Abstract
LetP andQ be two disjoint simple polygons havingm andn sides, respectively. We present an algorithm which determines whetherQ can be moved by a sequence of translations to a position sufficiently far fromP without colliding withP, and which produces such a motion if it exists. Our algorithm runs in timeO(mnα(mn) logm logn) where α(k) is the extremely slowly growing inverse Ackermann's function. Since in the worst case Ω(mn) translations may be necessary to separateQ fromP, our algorithm is close to optimal.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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.
B. Chazelle, A theorem on polygon cutting with applications,Proceedings of the 23th IEEE Symposium on Foundations of Computer Science, 339–349, 1982.
B. Chazelle, The polygon containment problem, inAdvances in Computing Research, Vol. I (F. P. Preparata, ed.), 1–32, JAI Press, 1983.
B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Proceedings of the ACM Symposium on Computational Geometry, 135–146, 1985.
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.
H. Edelsbrunner and E. Welzl, Private communication, 1985.
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.
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.
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.
S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes,Combinatorica 6 (1986), 151–177.
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.
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.
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.
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).
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.
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.
T. Lozano Perez and M. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles,Comm. ACM 22 (1979), 560–570.
J. R. Sack and G. Toussaint, Separability of pairs of polygons through single translations, manuscript.
S. Sifrony and M. Sharir, A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space,Algorithmica, to appear.
S. Suri, Finding minimum-link paths inside a simple polygon,Comput. Vision, Graphics Image Process., to appear.
R. E. Tarjan and C. Van Wyk, AnO(n log logn) time algorithm for triangulating simple polygons, manuscript, August 1986.
G. T. Toussaint, Movable separability of sets, inComputational Geometry (G. T. Toussaint, ed.), 335–375, North-Holland, Amsterdam, 1985.
C. K. Yap, How to Move a Chair Through a Door, Technical Report 238, Computer Science Department, Courant Institute, August 1986.
Author information
Authors and Affiliations
Additional information
Work on this paper by the first author has been supported by National Science Foundation Grant No. DMS-8501947. Work on this paper by the second author has been supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSP-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the second and third authors has also been supported by a grant from the joint Ramot-Israeli Ministry of Industry Foundation. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986.
Rights and permissions
About this article
Cite this article
Pollack, R., Sharir, M. & Sifrony, S. Separating two simple polygons by a sequence of translations. Discrete Comput Geom 3, 123–136 (1988). https://doi.org/10.1007/BF02187902
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187902