Research indexJournal article
凸多边形可移动性的最优判定算法
李
Science in China Series A-Mathematics Physics Astronomy & Technological Science (in Chinese)1 Dec 1987Open access
NobleIDark:/48914/w1/20260521/6FAF70F0DOI10.1360/za1987-17-12-1301
Journal articleOpen access
凸多边形可移动性的最优判定算法
李 · Science in China Series A-Mathematics Physics Astronomy & Technological Science (in Chinese) · 1987
NobleIDark:/48914/w1/20260521/6FAF70F0DOI10.1360/za1987-17-12-1301
Abstract
设 P =( p 0 ,p 1 ,…,p n-1 )和 Q =( q 0 ,q 1 ,…,q m-1 )为平面内互不相交的两个凸多边形,其顶点用笛卡儿坐标描述,并按顺时针次序列出.本文提出了两个基本问题: (1)对于任意给定的方向d,如何确定P是否可沿此方向无限移动而不与 Q 相碰撞; (2)如何确定 P 相对于 Q 的所有可移动方向.并分别给出了 O(log(n+ m)) 和 O(n+m) 的算法,在常数因子意义下,它们都是最优的.