Preprocessing chains for fast dihedral rotations is hard or even impossible.
From MaRDI portal
Publication:1410594
DOI10.1016/S0925-7721(02)00156-6zbMath1151.82446MaRDI QIDQ1410594
Michael Soss, Jeff Erickson, Mark H. Overmars
Publication date: 14 October 2003
Published in: Computational Geometry (Search for Journal in Brave)
polymerslower boundscollision detection3SUM-hardnessdihedral rotationdynamic querynonuniform algorithmstatic query
Statistical mechanics of polymers (82D60) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Related Items (5)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Motion planning algorithms for molecular simulations: a survey ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths
Cites Work
- On the general motion-planning problem with two degrees of freedom
- On a class of \(O(n^ 2)\) problems in computational geometry
- Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
- A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
- New Lower Bounds for Convex Hull Problems in Odd Dimensions
- Collision detection for deforming necklaces
- Efficient maintenance and self-collision testing for Kinematic Chains
This page was built for publication: Preprocessing chains for fast dihedral rotations is hard or even impossible.