确定两凸多边形可移动方向范围的最优算法

摘要：

设P与Q为平面上两个互不相交的凸多边形,其顶点个数分别为m与n.本文给出确定P相对Q的所有可移动方向范围的一个最优算法,其时间复杂度为O(logm+logn).本文算法虽然与文献”3”算法具有相同的渐进时间复杂度,但是由于本文算法在初始化过程中不必先求出两凸多边形的一条分离直线,所以在实际运行速度上比文献”3”算法要快.

关键词： 凸多边形 可移动方向 最优算法 计算几何

作者: 刘金义

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

会议类型: 国内会议

会议名称: 第一届全国几何设计与计算学术会议

会议地点: 山东青岛

会议语种:中文

页码: 221-227

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