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

关键词: 多边形, 凸多边形, 可移动性, 时间复杂性

Abstract: 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.

中图分类号: 

• TP391.4