统一确定两凸多边形支撑线的快速算法

A UNIFIED ALGORITHM FOR DETERMINING THE SUPPORTING LINES BETWEEN TWO CONVEX POLYGONS

设P与Q为平面上两个互不相交的凸多边形，则在P与Q之间必存在两条正支撑线和两条科支撑线，确定它们就可以确定P与Q的凸壳和P与Q的全部可移动方向，这在机器人学、几何布局及VLSI设计等领域具有重要实用意义。本文给出统一确定这些支撑线的快速算法，其时间复杂度为O（logm·logn），其中m与n分别为P与Q的顶点数。

Let P and Q be two arbitrary disjoint convex polygons on a plane. Between P and Q, theremust be two principal supporting lines and two oblique supporting lines. They are very critical todecide the convex hull of the union of P and Q and all directions along which P moves withoutcollision with Q. ttis paper gives a unified algorithm for efficiently determining all the foursupporting lines with the time complexity of (logm*logn), where m and n denoto the numer ofvertices of P and Q.