Preprocessing chains for fast dihedral rotations is hard or even impossible

Michael Soss, Jeff Erickson, Mark Overmars

Research output: Contribution to journalArticlepeer-review


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 subchains rigidly about the 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 Ω(nlogn) 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 Ω(n2) preprocessing is required to achieve sublinear query 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.

Original languageEnglish (US)
Pages (from-to)235-246
Number of pages12
JournalComputational Geometry: Theory and Applications
Issue number3
StatePublished - Nov 2003


  • 3sum-hardness
  • Collision detection
  • Lower bounds
  • Nonuniform algorithm

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Preprocessing chains for fast dihedral rotations is hard or even impossible'. Together they form a unique fingerprint.

Cite this