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

摘要：

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

关键词： 凸多边形 支撑线算法 凸壳

作者: 刘金义 程小茁

作者单位: 抚顺石油学院计算机科学与技术系

会议类型: 国内会议

会议名称: 第三届中国计算机图形学大会

会议地点: 杭州

会议语种:中文

页码: 52～58

在线出版日期: 2000-09-25（万方平台首次上网日期，不代表论文的发表时间）