判定简单多边形可移动方向的最优算法

摘要

设Ｐ＝（ｐ０，ｐ１，…，ｐｎ－１）和Ｑ＝（ｑ０，ｑ１，…，ｑｍ－１）是平面内两人凸包互不相交的简单多边形，本文研究了如何确定Ｐ相对于Ｑ的可移动方向问题，给出一种优于文献「１」的时间复杂度为Ｏ（ｎ＋ｍ）的最优算法。