Solving Geometric Puzzles With Divide And Concur

Other Titles


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.

Journal / Series

Volume & Issue



Date Issued




packing; constraint satisfaction; structure determination


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Elser, Veit

Committee Co-Chair

Committee Member

Sethna, James Patarasp
Thorne, Robert Edward

Degree Discipline


Degree Name

Ph. D., Physics

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record