Preprocessing chains for fast dihedral rotations
is hard or even impossible

Written with Mark Overmars and Michael A. Soss*.

Computational Geometry: Theory and Applications 26(3):235-246, 2003.

We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a dihedral rotation rotates one of these chains rigidly about this edge. The problem is to determine, given a chain, an edge, and an angle of rotation, if the motion can be performed without causing the chain to self-intersect. An Omega(n log n) lower bound on the time complexity of this problem is known.
     We prove that preprocessing a chain of n edges and answering n dihedral rotation queries is 3SUM-hard, giving strong evidence that solving n queries requires Omega(n2) time in the worst case. For dynamic queries, which also modify the chain if the requested dihedral rotation is feasible, we show that answering n queries is by itself 3SUM-hard, suggesting that sublinear query time is impossible after any amount of preprocessing.

Cross-eyed stereo view of a dihedral rotation

Publications - Jeff Erickson ( 04 Oct 2003