文献类型：期刊文章

作　　者：覃中平[1] 张焕国[2]

机构地区：[1]华中理工大学数学系,武汉430074 [2]武汉大学计算机科学系,武汉430072

出　　处：《计算机学报》

年　　份：1992

卷　　号：15

期　　号：3

起止页码：171-177

语　　种：中文

收录情况：BDHX、BDHX1992、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

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

关 键 词：图形学 算法  多边形 碰撞部位  

分 类 号：TP301.6]