Separating two simple polygons by a sequence of translations (Q1104080): Difference between revisions

Let P and Q be two disjoint simple (not necessarily convex) polygons. The authors 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. For earlier research on translational separability of planar objects, see \textit{G. T. Toussaint}, Computational geometry, Mach. Intell. Pattern Recognition 2, 335-375 (1985; Zbl 0588.68053).