Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible

Simple item page
dc.creatorSoss, Michael
dc.creatorErickson, Jeff
dc.creatorOvermars, Mark
dc.date2002-04-19
dc.date.accessioned2026-07-07T03:18:20Z
dc.date.available2026-07-07T03:18:20Z
dc.descriptionWe 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(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 answering n queries is by itself 3SUM-hard, suggesting that sublinear query time is impossible after any amount of preprocessing.
dc.description11 pages, 9 figures, see also http://www.cs.uiuc.edu/~jeffe/pubs/dihedral.html
dc.identifierhttps://arxiv.org/abs/cs/0204042
dc.identifierhttp://arxiv.org/abs/cs/0204042
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31071
dc.subjectComputational Geometry
dc.subjectF.2.2
dc.titlePreprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible
dc.typetext

Files

Collections

arXiv