未找到相关数据
凸多边形可移动性的最优判定算法
被引：23
作者：
李辉
机构：
[1] 南京大学计算机科学系
关键词：
凸多边形;
可移动性;
李辉;
定义;
顶点集;
判定算法;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
设P=(p0,p1,…,pn-1)和Q=(q0,q1,…,qm-1)为平面内互不相交的两个凸多边形,其顶点用笛卡儿坐标描述,并按顺时针次序列出.本文提出了两个基本问题: （1）对于任意给定的方向d,如何确定P是否可沿此方向无限移动而不与Q相碰撞; （2）如何确定P相对于Q的所有可移动方向.并分别给出了O(log（n+ m）)和O（n+m）的算法,在常数因子意义下,它们都是最优的.
引用
收藏
页码：1301 / 1308
页数：8
相关论文