SOLVING GEOMETRIC PUZZLES WITH DIVIDE AND CONCUR

In this dissertation we discuss a variety of geometric constraint satisfaction problems. The greatest part of the discussion is devoted to infinite packing problems, where the packing arrangement of an infinite number of congruent copies of an object with the greatest density is sought. We develop a general method, based on the Divide and Con-cur scheme, for discovering dense periodic packings of any convex object. We use this method to improve on the previous greatest known packing density of regular tetrahe-dra. We then generalize the discussion of regular tetrahedra to a one-parameter family of shapes interpolating between the regular tetrahedron and the sphere. We investigate how the likely optimal packing changes as the shape is changed and what continuous and abrupt transitions arise. We also use the method to reproduce the densest known lat-tice sphere packings and the best known lattice kissing arrangements in up to 14 and 11 dimensions respectively – the first such numerical evidence for their optimality in some of these dimensions. We then shift our discussion to the inverse problem of inferring the structure of biomolecules from a set of structural restraints derived from nuclear mag-netic resonance experiments. We describe a constraint-based approach which avoids the minimization of a cost/energy function and use it to reconstruct the structure of a beta-amyloid fibril formed by a 40-amino-acid peptide associated with Alzheimer’s dis-ease based on restraints published in the literature. Finally, we study a simple model of rippling in a two-dimensional atomic sheet due to bond length heterogeneity. We describe a form of dislocations which is not present in a homogeneous crystal and use a relationship between the dislocation density and the Gaussian curvature to characterize the relaxed conformation of the sheet. We find a relationship between this conformation and a surface in an abstract space associated with the combinatorial aspect of the bond length heterogeneity