Geometric and computational aspects of polymer reconfiguration

We examine a few computational geometric problems concerning the structures of polymers. We use a standard model of a polymer, a polygonal chain (path of line segments) in three dimensions. The chain can be reconfigured in an y manner as long: as the edge lengths and the angles between consecutive ed ges remain fixed, and no two edges cross during the motion. We discuss prel iminary results on the following problems. Given a chain, select some interior edge (uv) over bar, defining two subcha ins which are adjacent to (uv) over bar. We keep the two subchains individu ally rigid and rotate one around (uv) over bar while leaving the other fixe d in space, while maintaining the vertex-angles at (uv) over bar. We call t his motion an edge spin at (uv) over bar. An O(n(2)) algorithm for this pro blem is given as well as an Omega (n log n) lower bound on the time complex ity. In determining whether a chain can be reconfigured from one conformation to another, it is useful to consider reconfiguring through some canonical con formation. In our three-dimensional case, the most obvious choice is to fla tten a chain into the plane. However, we demonstrate that determining if a given chain can be reconfigured into the plane without self-intersecting is NP-hard, even if the restriction that it must lie monotonically is added. We then provide an O(n) algorithm to decide if a chain has a non-crossing c onvex coil conformation (where all angles turn in the same direction), alth ough we cannot yet decide if a sequence of motions to reconfigure a chain i nto a convex coil conformation exists.