Document Open Access Logo

Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace

Authors Mikkel Abrahamsen, Bartosz Walczak

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.4.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Mikkel Abrahamsen
Bartosz Walczak

Cite As Get BibTex

Mikkel Abrahamsen and Bartosz Walczak. Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.4

Abstract

We describe the first algorithm to compute the outer common tangents of two disjoint 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 on the same side of the line. An outer common tangent of two polygons is a tangent of both polygons such that the polygons lie on the same side of the tangent. Each polygon is given as a read-only array of its corners in cyclic order. The algorithm detects if an outer common tangent does not exist, which is the case if and only if the convex hull of one of the polygons is contained in the convex hull of the other. Otherwise, two corners defining an outer common tangent are returned.

Subject Classification

Keywords
  • simple polygon
  • common tangent
  • optimal algorithm
  • constant workspace

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Abrahamsen. An optimal algorithm computing edge-to-edge visibility in a simple polygon. In 25th Canadian Conference on Computational Geometry (CCCG 2013), pages 157-162, 2013. Google Scholar
  2. M. Abrahamsen. An optimal algorithm for the separating common tangents of two polygons. In 31st International Symposium on Computational Geometry (SoCG 2015), volume 34 of LIPIcs, pages 198-208, 2015. http://arxiv.org/abs/1511.04036 (corrected version).
  3. T. Asano, K. Buchin, M. Buchin, M. Korman, W. Mulzer, G. Rote, and A. Schulz. Memory-constrained algorithms for simple polygons. Comput. Geom., 46(8):959-969, 2013. Google Scholar
  4. T. Asano, W. Mulzer, G. Rote, and Y. Wang. Constant-work-space algorithms for geometric problems. J. Comput. Geom., 2(1):46-68, 2011. Google Scholar
  5. L. Barba, M. Korman, S. Langerman, K. Sadakane, and R.I. Silveira. Space-time trade-offs for stack-based algorithms. Algorithmica, 72(4):1097-1129, 2015. Google Scholar
  6. L. Barba, M. Korman, S. Langerman, and R.I. Silveira. Computing the visibility polygon using few variables. Comput. Geom., 47(9):918-926, 2014. Google Scholar
  7. G.S. Brodal and R. Jacob. Dynamic planar convex hull. In 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), pages 617-626, 2002. Google Scholar
  8. E. Carson, J. Demmel, L. Grigori, N. Knight, P. Koanantakool, O. Schwartz, and H.V. Simhadri. Write-avoiding algorithms. Technical Report http://www.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-163.html, University of California, Berkeley, 2015.
  9. O. Darwish and A. Elmasry. Optimal time-space tradeoff for the 2D convex-hull problem. In European Symposium on Algorithms (ESA 2014), volume 8737 of LNCS, pages 284-295. Springer, 2014. Google Scholar
  10. L. Guibas, J. Hershberger, and J. Snoeyink. Compact interval trees: a data structure for convex hulls. Int. J. Comput. Geom. Appl., 1(1):1-22, 1991. Google Scholar
  11. S. Har-Peled. Shortest path in a polygon using sublinear space. In 31st International Symposium on Computational Geometry (SoCG 2015), volume 34 of LIPIcs, pages 111-125, 2015. Google Scholar
  12. J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. BIT Numer. Math., 32(2):249-267, 1992. Google Scholar
  13. D. Kirkpatrick and J. Snoeyink. Computing common tangents without a separating line. In 4th International Workshop on Algorithms and Data Structures (WADS 1995), volume 955 of LNCS, pages 183-193. Springer, 1995. Google Scholar
  14. M. Korman, W. Mulzer, A. van Renssen, M. Roeloffzen, P. Seiferth, and Y. Stein. Time-space trade-offs for triangulations and voronoi diagrams. In Workshop on Algorithms and Data Structures (WADS 2015), volume 9214 of LNCS, pages 482-494. Springer, 2015. Google Scholar
  15. A.A. Melkman. On-line construction of the convex hull of a simple polyline. Inform. Process. Lett., 25(1):11-12, 1987. Google Scholar
  16. M.H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. System Sci., 23(2):166-204, 1981. Google Scholar
  17. F.P. Preparata and S.J. Hong. Convex hulls of finite sets of points in two and three dimensions. Commun. ACM, 20(2):87-93, 1977. Google Scholar
  18. G.T. Toussaint. Solving geometric problems with the rotating calipers. In IEEE Mediterranean Electrotechnical Conference (MELECON 1983), pages A10.02/1-4, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact