An Improved Gilbert Algorithm with Rapid Convergence

摘要

Gilbert algorithm is a very popular algorithm in collision detection in robotics and also in classification in pattern recognition. However, the major drawback of Gilbert algorithm is that in many cases it becomes very slow as it approaches the final solution and the vertices selection vibrates in these cases. In this paper: a) It is proven theoretically that when the selection of vertices vibrates among several points, the algorithm will converge to the hyperplane determined by these points. b) Based on the above results, an improved Gilbert algorithm for computing the distance between two convex polytopes is presented. The algorithm can avoid the slow convergence of the original one. Numerical simulation results demonstrate the effectiveness and advantage of the improved algorithm