H-Walk
- 13 June 1999
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 265-273
- https://doi.org/10.1145/304893.304979
Abstract
This paper presents the Hierarchical Walk, or H-Walk al- gorithm, which maintains the distance between two moving convex bodies by exploiting both motion coherence and hi- erarchical representations. For convex polygons, we prove that H-Walk improves on the classic Lin-Canny and Dobkin- Kirkpatrick algorithms. We have implemented H-Walk for moving convex polyhedra in three dimensions. Experimen- tal results indicate that, unlike previous incremental dis- tance computation algorithms, H-Walk adapts well to vari- able coherence in the motion.Keywords
This publication has 10 references indexed in Scilit:
- Efficient distance computation between non-convex objectsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A fast algorithm for incremental distance calculationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Enhancing GJK: computing minimum and penetration distances between convex polyhedraPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- OBBTreePublished by Association for Computing Machinery (ACM) ,1996
- Collision detection for interactive graphics applicationsIEEE Transactions on Visualization and Computer Graphics, 1995
- I-COLLIDEPublished by Association for Computing Machinery (ACM) ,1995
- A fast procedure for computing the distance between complex objects in three-dimensional spaceIEEE Journal on Robotics and Automation, 1988
- A linear algorithm for determining the separation of convex polyhedraJournal of Algorithms, 1985
- Computing the extreme distances between two convex polygonsJournal of Algorithms, 1985
- A new representation for linear listsPublished by Association for Computing Machinery (ACM) ,1977