一种判定简单多边形与凸多边形可移动性的算法

摘要

设简单多边形P=(P0,P1,…,Pn-1的凸包和凸多边形Q=(q0,q1,…qm-1互不相交。研究了P相对于Q的可移动性问题,提出了一种在最坏情况下时间复杂性为O（n+m）的算法,它在不计常数因子的情况下是最优的。