LIPIcs.SOCG.2015.198.pdf
- Filesize: 447 kB
- 11 pages
Document
An Optimal Algorithm for the Separating Common Tangents of Two Polygons
Author
-
Part of:
Volume:
31st International Symposium on Computational Geometry (SoCG 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-06-12
Cite As Get BibTex
Mikkel Abrahamsen. An Optimal Algorithm for the Separating Common Tangents of Two Polygons. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 198-208, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.198
Abstract
We describe an algorithm for computing the separating common tangents of two simple polygons using linear time and only constant workspace. A tangent of a polygon is a line touching the polygon such that all of the polygon lies to the same side of the line. A separating common tangent of two polygons is a tangent of both polygons where the polygons are lying on different sides of the tangent. Each polygon is given as a read-only array of its corners. If a separating common tangent does not exist, the algorithm reports that. Otherwise, two corners defining a separating common tangent are returned. The algorithm is simple and implies an optimal algorithm for deciding if the convex hulls of two polygons are disjoint or not. This was not known to be possible in linear time and constant workspace prior to this paper. An outer common tangent is a tangent of both polygons where the polygons are on the same side of the tangent. In the case where the convex hulls of the polygons are disjoint, we give an algorithm for computing the outer common tangents in linear time using constant workspace.
Subject Classification
Keywords
- planar computational geometry
- simple polygon
- common tangent
- optimal algorithm
- constant workspace
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
M. Abrahamsen. An optimal algorithm computing edge-to-edge visibility in a simple polygon. In Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG, pages 157-162, 2013.
-
T. Asano, K. Buchin, M. Buchin, M. Korman, W. Mulzer, G. Rote, and A. Schulz. Memory-constrained algorithms for simple polygons. Computational Geometry: Theory and Applications, 46(8):959-969, 2013.
-
T. Asano, W. Mulzer, G. Rote, and Y. Wang. Constant-work-space algorithms for geometric problems. Journal of Computational Geometry, 2(1):46-68, 2011.
-
L. Barba, M. Korman, S. Langerman, and R.I. Silveira. Computing the visibility polygon using few variables. In Proceedings of the 22nd International Symposium on Algorithms and Computation, ISAAC, volume 7014 of Lecture Notes in Computer Science, pages 70-79. Springer, 2011.
-
G.S. Brodal and R. Jacob. Dynamic planar convex hull. In Proceedings of the 43rd annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 617-626, 2002.
-
R.L. Graham and F.F. Yao. Finding the convex hull of a simple polygon. Journal of Algorithms, 4(4):324-331, 1983.
-
Leonidas Guibas, John Hershberger, and Jack Snoeyink. Compact interval trees: A data structure for convex hulls. International Journal of Computational Geometry & Applications, 1(1):1-22, 1991.
-
J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. BIT Numerical Mathematics, 32(2):249-267, 1992.
-
D. Kirkpatrick and J. Snoeyink. Computing common tangents without a separating line. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, WADS, volume 955 of Lecture Notes in Computer Science, pages 183-193. Springer, 1995.
-
A.A. Melkman. On-line construction of the convex hull of a simple polyline. Information Processing Letters, 25(1):11-12, 1987.
-
M.H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23(2):166-204, 1981.
-
F.P. Preparata and S.J. Hong. Convex hulls of finite sets of points in two and three dimensions. Communications of the ACM, 20(2):87-93, 1977.
-
G.T. Toussaint. Solving geometric problems with the rotating calipers. In Proceedings of the IEEE Mediterranean Electrotechnical Conference, MELECON, pages A10.02/1-4, 1983.