is hard or even impossible

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

arXiv:cs.CG/0204042

- Download journal version (final except for copy-editing, © Elsevier Science B.V. 2002):
- Official journal version from ScienceDirect (institutional subscription required)

Abstract:

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 adihedral rotationrotates 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(nlogn) lower bound on the time complexity of this problem is known.

We prove that preprocessing a chain ofnedges and answeringndihedral rotation queries is 3SUM-hard, giving strong evidence that solvingnqueries requires Omega(n^{2}) time in the worst case. For dynamic queries, which also modify the chain if the requested dihedral rotation is feasible, we show that answeringnqueries is by itself 3SUM-hard, suggesting that sublinear query time is impossible afteranyamount of preprocessing.Cross-eyed stereo view of a dihedral rotation

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 04 Oct 2003