Geometric and computational aspects of molecular reconfiguration

We examine geometric problems of reconfiguring molecules modeled by polygons and polygonal chains in two and three dimensions. The molecule can be continuously reconfigured as long as the edge lengths are maintained and the object does not self-intersect.;We begin with a treatment of polygons in chapters 3 and 4. We prove that in two dimensions all convex configurations of a given polygon are reachable from any other and provide an efficient algorithm for convexifying planar monotone polygons. We also describe an algorithm to convexity three-dimensional polygons with simple projections.;We further prove that the motions to bring a convex configuration to another can be accomplished in three-dimensions by a series of restrictive moves called pivots, which are widely used in the polymer physics community. A pivot is a motion by which a contiguous subchain of the polygon is rotated about the line through its endpoints. A particular type of pivot on a planar polygon, known as a deflation, splits the polygon into two linearly separable subchains and rotates one by 180°. (A deflation can be thought of as the inverse of a flip as defined by Erdos [49].) Since a rotation of 180° about a line is equivalent to a reflection, a planar polygon remains planar after the deflation. In 1993 [164], Wegner conjectured that a planar polygon could admit only a finite number of deflations before self-intersecting. We disprove this conjecture by exhibiting a counterexample.;In chapters 5 through 7, we consider only polygonal chains in three-dimensions. As is consistent with the conventions of the chemistry and physics communities, we augment our model by allowing only those motions which maintain the angles at the vertices of the chain (and which also maintain the edge lengths and do not cause self-intersection). The chain can be reconfigured by only altering the dihedral torsion angles, which better reflects the fixed bond angles of a molecule.;We discuss several computational problems on this model. First, we describe an algorithm to determine the feasibility of the simplest possible motion---the alteration of only one dihedral angle---called a dihedral rotation. Since molecular reconfiguration is a complex process, the motion of a chain would involve a vast number of dihedral rotations. We prove lower bounds on the computational complexity of preprocessing a polygonal chain to determine the feasibility of multiple rotations.;We continue by demonstrating the intractability of several questions: (1) computing the maximum possible and minimum possible distance between the endpoints of the chain, (2) determining whether a chain can be reconfigured to certain canonical configurations, and (3) determining configurational chirality, that is, whether or not a chain can be reconfigured into its mirror image. This last problem has important implications for drug design, since the two mirror images of a molecule can have radically different properties.