Solving Geometric Puzzles With Divide And Concur

Abstract

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 Concur 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 tetrahedra. 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 lattice 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 magnetic 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 disease 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.