返回Google圖書搜尋

Separating Two Simple Polygons by a Sequence of Translations

R. PollackM. SharirCourant Institute of Mathematical Sciences. Computer Science DepartmentS. Sifrony

出版	New York University, Courant Institute of Mathematical Sciences, Computer Science Division, 1986
URL	http://books.google.com.hk/books?id=XrunHwAACAAJ&hl=&source=gbs_api

註釋Abstract: "Let P and Q be two disjoint simple polygons having m and n sides respectively. We present an algorithm which determines whether Q can be moved by a sequence of translations to a position sufficiently far from P without colliding with P, and which produces such a motion if it exists. Our algorithm runs in time O(mn [alpha](mn) log m log n) where [alpha](k) is the extremely slowly growing inverse Ackermann's function. Since in the worst case [omega](mn) translations may be necessary to separate Q from P, our algorithm is close to optimal."