Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible

Details Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible

2002-04-19

arxiv.org/abs/cs/0204042v1

Computer Science

Computational Geometry

11 pages, 9 figures, see also http://www.cs.uiuc.edu/~jeffe/pubs/dihedral.html

Scientific paper

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(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.

Affiliated with

Also associated with

No associations

Rating

Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-280572