确定凸多边形平移时最初碰撞部位的最优算法

被引：25

作者：

覃中平

张焕国

机构：

[1] 华中理工大学数学系,武汉大学计算机科学系武汉,武汉

来源：

计算机学报 | 1992年 / 03期

关键词：

图形学; 算法; 多边形; 碰撞;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

本文提出在图形学,机器人学,VLSI设计与CAD/CAM等众多领域中具有广泛应用的下述基本问题:设P与Q为平面内分别具有m与n个顶点的凸多边形,若P沿给定方向d移动将与Q相碰撞,如何根据P与Q的顶点坐标事先确定P与Q相碰撞时两者上的最初碰撞的顶点和边.利用折半搜索技术,本文给出了求解此基本问题的时间复杂度为O(logm+logn)的算法并证明这一算法在时间上是最优的.

引用

页码：171 / 177

页数：7