An Optimal Algorithm for Solving Collision Distance Between Convex Polygons in Plane

摘要

In this paper,we study the problem of calculating th minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and proprties are explored,then an optimal algorithm OPFIV with time complexity O(log+n+m)) is developed and its correctness and optimization are proved rigorously.