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 any manner as long as the edge lengths and the angles between consecutive edges remain fixed, and no two edges cross during the motion. We discuss preliminary results on the following problems. Given a chain, select some interior edge uv, defining two subchains which are adjacent to uv. We keep the two subchains individually rigid and rotate one around uv while leaving the other fixed in space, while maintaining the vertex-angles at uv. We call this motion an edge spin at uv. An O(n²) algorithm for this problem is given as well s an Ω (n log n) lower bound on the time complexity. In determining whether a chain can be reconfigured from one conformation to another, it is useful to consider reconfiguring through some canonical conformation. In our three-dimensional case, the most obvious choice is to flatten 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 convex coil conformation (where all angles turn in the same direction), although we cannot yet decide if a sequence of motions to reconfigure a chain into a convex coil conformation exists.