A fast algorithm for incremental distance calculation
Top Cited Papers
- 10 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1008-1014
- https://doi.org/10.1109/robot.1991.131723
Abstract
A simple and efficient algorithm for finding the closest points between two convex polynomials is described. Data from numerous experiments tested on a broad set of convex polyhedra on R/sup 3/ show that the running time is roughly constant for finding closest points when nearest points are approximately known and is linear in total number of vertices if no special initialization is done. This algorithm can be used for collision detection, computation of the distance between two polyhedra in three-dimensional space, and other robotics problems. It forms the heart of the motion planning algorithm previously presented by the authors (Proc. IEEE ICRA, p.1554-9, 1990).Keywords
This publication has 17 references indexed in Scilit:
- Linear programming and convex hulls made easyPublished by Association for Computing Machinery (ACM) ,1990
- Computing the distance between general convex objects in three-dimensional spaceIEEE Transactions on Robotics and Automation, 1990
- Determining the minimum translational distance between two convex polyhedraPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- A linear algorithm for determining the separation of convex polyhedraJournal of Algorithms, 1985
- Motion Planning with Six Degrees of Freedom. RevisionPublished by Defense Technical Information Center (DTIC) ,1984
- Linear Time Algorithms for Two- and Three-Variable Linear ProgramsSIAM Journal on Computing, 1984
- Linear Programming in Linear Time When the Dimension Is FixedJournal of the ACM, 1984
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related ProblemsSIAM Journal on Computing, 1983
- Minimum distances for robot task simulationRobotica, 1983
- Finding the nearest point in A polytopeMathematical Programming, 1976