Abstract
LetP andQ be two disjoint simple polygons havingn sides each. We present an algorithm which determines whetherQ can be moved by a single translation to a position sufficiently far fromP, and which produces all such motions if they exist. The algorithm runs in timeO(t(n)) wheret(n) is the time needed to triangulate ann-sided polygon. Since Tarjan and Van Wyk have recently shown thatt(n)=O(n log logn) this improves the previous best result for this problem which wasO(n logn) even after triangulation.
Article PDF
Similar content being viewed by others
References
L. J. Guibas and F. F. Yao, On translating a set of rectangles,Proc. Twelfth Annual ACM Symposium on Theory of Computing, 154–160 (1980).
T. Ottman and P. Widmayer, On translating a set of line segments,Computer Vision, Graphics and Image Processing, Vol. 24, 382–389 (1983).
G. T. Toussaint, The complexity of movement,Proc. IEEE International Symposium on Information Theory, St. Jovite (September 1983).
J.-R. Sack and G. T. Toussaint, Movability of objects,Proc. IEEE International Symposium on Information Theory, St. Jovite (September 1983).
G. T. Toussaint and J.-R. Sack, Some new results on moving polygons in the plane,Proc. Robotic Intelligence and Productivity Conference, Detroit, Michigan, 158–163 (November 18–19, 1983).
B. Chazelleet al., The complexity and decidability of SEPARATION, Technical Report CS-83-34, University of Waterloo (November 1983).
G. T. Toussaint, On translating a set of polyhedra,Proc. Conference on Polyhedra, Smith College, Northampton, Massachusetts (April 6–8, 1984).
R. Dawson, On removing a ball without disturbing the others,Mathematics Magazine, Vol. 57, No. 1, 27–30 (January 1984).
K. Post, Six interlocking cylinders with respect to all directions, Internal manuscript, University of Eindhoven (December 1983).
W. Moser, Research problems in discrete geometry, Department of Mathematics, McGill University (1981).
G. T. Toussaint, Some collision avoidance problems between spheres,Proc. International Conference on Systems, Man and Cybernetics, Tucson, Arizona (November 1985).
Van-Duc Nguyen, The find-path problem in the plane, A.I. Memo, No. 160, Artificial Intelligence Laboratory, M.I.T. (February 1984).
Bruce R. Donald, Hypothesizing channels through free-space in solving the findpath problem, A.I. Memo, No. 736, Artificial Intelligence Laboratory, M.I.T. (June 1983).
David Marr and Lucia Vaina, Representation and recognition of the movement of shapes, A.I. Memo, No. 597, Artificial Intelligence Laboratory, M.I.T. (October 1980).
G. T. Toussaint, Movable separability of sets, inComputational Geometry, G. T. Toussaint, Ed., North-Holland, Amsterdam, 335–375 (1985).
S. Whitesides, Computational geometry and spatial planning, inComputational Geometry, G. T. Toussaint, Ed., North-Holland, Amsterdam, 377–427 (1985).
G. T. Toussaint and H. ElGindy, Separation of two monotone polygons in linear time,Robotica, Vol. 2, 215–220 (1984).
J.-R. Sack and G. T. Toussaint, Translating polygons in the plane,Proc. STACS '85, Saarbrucken (January 1985).
J.-R. Sack and G. T. Toussaint, Separability of pairs of polygons through single translations,Robotica, Vol. 5, 55–63 (1987).
D. Kirkpatrick, Optimal search in planar subdivisions,SIAM Journal on Computing, Vol. 12, 28–35 (February 1983).
R. Pollack, M. Sharir, and S. Sifrony, Separating two simple polygons by a sequence of translations,Discrete and Computational Geometry, Vol. 3, 123–136 (1988).
C. Lantuejoul and F. Maisonneuve, Geodesic methods in quantitative image analysis,Pattern Recognition, Vol. 17, 1177–1187 (1984).
D. T. Lee and F. P. Preparata, Euclidean shortest paths in the presence of rectilinear barriers,Networks, Vol. 14, 393–410 (1984).
G. T. Toussaint, Shortest path solves edge-to-edge visibility in a polygon,Pattern Recognition Letters, Vol. 4, 165–170 (July 1986).
B. Chazelle, A theorem on polygon cutting with applications,Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, 339–349 (1982).
H. ElGindy, Hierarchical decomposition of polygons with applications, Ph.D. thesis, School of Computer Science, McGill University (May 1985).
L. M. Kelly, Ed.,The Geometry of Metric and Linear Spaces, Springer-Verlag, New York, (1985).
K. Hoffman, K. Melhorn, P. Rosenstiehl, and R. E. Tarjan, Sorting Jordan sequences in linear time,Proc. Symposium on Computational Geometry, Baltimore, Maryland, 196–203 (June 1985).
L. J. Guibas and J. Stolfi, Notes on computational geometry, Stanford University (1982).
B. K. Bhattacharya and G. T. Toussaint, AnO(n log logn) time algorithm for determining translation separability of two simple polygons, Technical Report No. SOCS-86.1, McGill University (January 1986).
F. P. Preparata and K. J. Supowit, Testing a simple polygon for monotonicity,Information Processing Letters, Vol. 12, 161–164 (August 1981).
R. E. Tarjan and C. J. Van Wyk, AnO(n log logn) time algorithm for triangulating simple polygons,SIAM Journal on Computing, in press.
J. Kahn, M. Klawe, and D. Kleitman, Traditional galleries require fewer watchmen,SIAM Journal on Algebraic and Discrete Methods, Vol. 4, 194–206 (June 1983).
D. McCallum and D. Avis, A linear time algorithm for finding the convex hull of a simple polygon,Information Processing Letters, Vol. 8, 201–205 (1979)
B. M. Chazelle and D. P. Dobkin, Detection is easier than computation,Proc. 12th SIGACT Symposium, Los Angeles, California (1980).
G. T. Toussaint, Solving geometric problems with the rotating calipers,Proc. MELECON '83, Athens (May 1983).
G. T. Toussaint, Shortest path solves translation separability of polygons, Technical Report SOCS-85.27, McGill University (October 1985).
Author information
Authors and Affiliations
Additional information
This research was supported by NSERC Grant A9293, FCAR Grant EQ-1678, and a Killam Fellowship from the Canada Council.
Rights and permissions
About this article
Cite this article
Toussaint, G. On separating two simple polygons by a single translation. Discrete Comput Geom 4, 265–278 (1989). https://doi.org/10.1007/BF02187729
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187729