Abstract: Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algorithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.

Key words: Computational geometry, Polygon, Voronoi diagram, Distance computation

Please provide your name, email address and a comment

Your Name: Affili: E-Mail Address:

Comment (Please comment in English):


Verification Code(click to change a pic):