Please use this identifier to cite or link to this item:
Title: Fast versions of the Gilbert-Johnson-Keerthi distance algorithm: Additional results and comparisons
Authors: Ong, C.J. 
Gilbert, E.G.
Issue Date: Aug-2001
Citation: Ong, C.J.,Gilbert, E.G. (2001-08). Fast versions of the Gilbert-Johnson-Keerthi distance algorithm: Additional results and comparisons. IEEE Transactions on Robotics and Automation 17 (4) : 531-539. ScholarBank@NUS Repository.
Abstract: This paper considers fast algorithms for computing the Euclidean distance between objects that are modeled by convex polytopes in three-dimensional space. The algorithms, designated by RGJK, are modifications of the Gilbert-Johnson-Keerthi algorithm that follow the scheme originated by Cameron. Each polytope is represented by its vertices and a list of adjacent vertices for each vertex. When the algorithms are appropriately applied to a pair of objects that have small incremental motions, they share the advantage of the closest-feature algorithm introduced by Lin and Canny: computational time is very small and does not depend significantly on the total number of object vertices. However, when the objects contain complex vertices or faces, the time can increase drastically. Reasons for this problem are analyzed and algorithmic fixes for them are given. Other contributions to algorithmic performance include a procedure for reducing computational time in the presence of collisions. Comprehensive numerical experiments illuminate the dependence of computational time on algorithmic details, object complexity, and the size of incremental motions. The experiments include direct comparisons of RGJK with the closest-feature algorithms of Lin and Canny and of Mirtich.
Source Title: IEEE Transactions on Robotics and Automation
ISSN: 1042296X
DOI: 10.1109/70.954768
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Nov 16, 2018

Page view(s)

checked on Nov 17, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.