摘要
设P=(p_0,p_1,…,p_(n-1))与Q=(q_0,q_1,…,q_(n-1))是任二互不相交的凸多边形,本文研究了如何快速确定它们的可碰撞区域和可移动区域的问题. 文中提出了可碰撞性判定的新方法,研究了斜支撑线的基本性质,利用这些性质构造出了求斜支撑线的快速算法,其时间复杂度为O(log^2(n+m)),在此基础上给出了确定可碰撞区域和可移动区域的时间复杂度为O(log^2(n+m))的快速算法.
出处
《中国科学（A辑）》
CSCD
1992年第7期753-762,共10页
Science in China(Series A)
