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