Title :
Enhancing GJK: computing minimum and penetration distances between convex polyhedra
Author :
Cameron, Stephen
Author_Institution :
Comput. Lab., Oxford Univ., UK
Abstract :
The problem of tracking the distance between two convex polyhedra is finding applications in many areas of robotics, including intersection detection, collision detection, and path planning. We present new results that confirm an almost-constant time complexity for an enhanced version of Gilbert, Johnson and Keerthi´s (GJK) algorithm, and also describe modifications to the algorithm to compute measures of penetration distance
Keywords :
computational complexity; computational geometry; path planning; robots; tracking; GJK algorithm; Gilbert-Johnson-Keerthi algorithm; collision detection; configuration space; convex polyhedra; minimum distance; path planning; penetration distance; robotics; time complexity; Algorithm design and analysis; Analytical models; Computational modeling; Laboratories; Object detection; Orbital robotics; Path planning; Road accidents; Robots; Time measurement;
Conference_Titel :
Robotics and Automation, 1997. Proceedings., 1997 IEEE International Conference on
Conference_Location :
Albuquerque, NM
Print_ISBN :
0-7803-3612-7
DOI :
10.1109/ROBOT.1997.606761
