节点文献
确定两凸多边形可移动方向范围的最优算法
【作者】 刘金义；
【机构】 抚顺石油学院计算机科学与技术系；
【摘要】 设P与Q为平面上两个互不相交的凸多边形,其顶点个数分别为m与n。本文给出确定P相对Q的所有可移动方向范围的—个最优算法,其时间复杂度为O(logm+logn)。本文算法虽然与文献[3]算法具有相同的渐进时间复杂度,但是由于本文算法在初始化过程中不必先求出两凸多边形的一条分离直线,所以在实际运行速度上比文献[3]算法要快。
- 【会议录名称】 第一届全国几何设计与计算学术会议论文集
- 【会议名称】第一届全国几何设计与计算学术会议
- 【会议时间】2002-06-01
- 【会议地点】中国山东青岛
- 【分类号】TP301.6;O224
- 【主办单位】中国工业与应用数学学会几何设计与计算专业委员会