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

An Algorithm for Deciding Movable Directions of a Polygon and a Convex Polygon

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

Let the convex hull of a polygon P = (P0, P,1 …, Pn-1)and a convex polygon Q=(q0, q1, … qm-1)be disjoint in a plane, this paper studies the problem of deciding all movable directions when P moves and doesn't collide against Q(or Q moves and doesn't collide against P).An algorithm is described with the time-complexity O(n+m) in the worst case, and it is optimal without ragard for constant factors.