A fast procedure for computing the distance between complex objects in three space
- 23 March 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 4, 1883-1889
- https://doi.org/10.1109/robot.1987.1087825
Abstract
An efficient and reliable algorithm for computing the Euclidean distance between a pair of convex sets in Rmdescribed. Extensive numerical experience with a broad family of polytopes in Rsshows that the computational cost is approximately linear in the total number of vertices specifying the two polytopes. The algorithm has special features which make its application in a variety of robotics problems attractive. These are discussed and an example of collision detection is given.Keywords
This publication has 23 references indexed in Scilit:
- On motion planning with six degrees of freedom: Solving the intersection problems in configuration spacePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Real-Time Obstacle Avoidance for Manipulators and Mobile RobotsThe International Journal of Robotics Research, 1986
- A collision detection algorithm based on velocity and distance boundsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Minimum time robot path planning in the presence of obstaclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- A linear algorithm for determining the separation of convex polyhedraJournal of Algorithms, 1985
- A subdivision algorithm in configuration space for findpath with rotationIEEE Transactions on Systems, Man, and Cybernetics, 1985
- Distance functions and their application to robot path planning in the presence of obstaclesIEEE Journal on Robotics and Automation, 1985
- On the “piano movers'” problem I. The case of a two‐dimensional rigid polygonal body moving amidst polygonal barriersCommunications on Pure and Applied Mathematics, 1983
- Finding the minimum distance between two convex polygonsInformation Processing Letters, 1981
- An Iterative Procedure for Computing the Minimum of a Quadratic Form on a Convex SetSIAM Journal on Control, 1966