Separating two simple polygons by a sequence of translations. (English) Zbl 0646.68052

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 G. T. Toussaint, Computational geometry, Mach. Intell. Pattern Recognition 2, 335-375 (1985; Zbl 0588.68053).
Reviewer: E.J.F.Primrose


68Q25 Analysis of algorithms and problem complexity
51M20 Polyhedra and polytopes; regular figures, division of spaces
52A10 Convex sets in \(2\) dimensions (including convex curves)
51M15 Geometric constructions in real or complex geometry


Zbl 0588.68053
Full Text: DOI EuDML


[1] B. K. Bhattacharya and G. T. Toussaint, A Linear Algorithm for Determining Translation Separability of Two Simple Polygons, Technical Report SOCS-86.1, McGill University, 1986.
[2] B. Chazelle, A theorem on polygon cutting with applications,Proceedings of the 23th IEEE Symposium on Foundations of Computer Science, 339-349, 1982.
[3] B. Chazelle, The polygon containment problem, inAdvances in Computing Research, Vol. I (F. P. Preparata, ed.), 1-32, JAI Press, 1983.
[4] B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Proceedings of the ACM Symposium on Computational Geometry, 135-146, 1985. · Zbl 0695.68033
[5] L. P. Chew and R. L. Drysdale, III, Voronoi diagrams based on convex distance functions,Proceedings of the ACM Symposium on Computational Geometry, 235-244, 1985.
[6] H. Edelsbrunner and E. Welzl, Private communication, 1985.
[7] S. Fortune, A fast algorithm for polygon containment by translation,Proceedings of the 12th International Colloquium on Automata, Languages and Programming, 189-198, Lecture Notes in Computer Science, Vol. 194, Springer-Verlag, New York, 1985. · Zbl 0571.68029
[8] L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, Linear time algorithms for shortest path and visibility problems inside simple polygons.Proceedings of the second ACM Symposium on Computational Geometry, 1-13, 1986. · Zbl 0642.68081
[9] L. Guibas, L. Ramshaw, and J. Stolfi, A kinetic framework for computational geometry,Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, 100-111, 1983.
[10] S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica6 (1986), 151-177. · Zbl 0636.05003 · doi:10.1007/BF02579170
[11] K. Kedem, and M. Sharir, An efficient algorithm for planning translational collision-free motion of a convex polygonal object in 2-dimensional space admidst polygonal obstacles,Proceedings of the ACM Symposium on Computational Geometry, 75-80, 1985.
[12] K. Kedem and M. Sharir, An Efficient Motion Planning Algoritm for a Convex Rigid Polygonal Object in 2-Dimensional Polygonal Space, Technical Report 253, Computer Science Department, Courant Institute, October 1986. · Zbl 0688.68039
[13] K. Kedem, R. Livne, J. Pach, and M. Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles,Discrete Comput. Geom.1 (1986), 59-72. · Zbl 0594.52004 · doi:10.1007/BF02187683
[14] D. Leven and M. Sharir, An efficient and simple motion-planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers,Proceedings of the ACM Symposium on Computational Geometry, 221-227, 1985 (also to appear inJ. Algorithms).
[15] D. Leven and M. Sharir, Planning a purely translational motion of a convex object in two-dimensional space using generalized Voronoi diagrams,Discrete Comput. Geom.2 (1987), 9-31. · Zbl 0606.52002 · doi:10.1007/BF02187867
[16] D. Leven and M. Sharir, On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space,Discrete Comput. Geom., to appear. · Zbl 0616.52009
[17] T. Lozano Perez and M. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles,Comm. ACM22 (1979), 560-570. · doi:10.1145/359156.359164
[18] J. R. Sack and G. Toussaint, Separability of pairs of polygons through single translations, manuscript.
[19] S. Sifrony and M. Sharir, A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space,Algorithmica, to appear. · Zbl 0643.68049
[20] S. Suri, Finding minimum-link paths inside a simple polygon,Comput. Vision, Graphics Image Process., to appear. · Zbl 0624.68101
[21] R. E. Tarjan and C. Van Wyk, AnO(n log logn) time algorithm for triangulating simple polygons, manuscript, August 1986. · Zbl 0659.68068
[22] Toussaint, G. T.; Toussaint, G. T. (ed.), Movable separability of sets, 335-375 (1985), Amsterdam · Zbl 0588.68053
[23] C. K. Yap, How to Move a Chair Through a Door, Technical Report 238, Computer Science Department, Courant Institute, August 1986.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.