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

摘要

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