Document Open Access Logo

Circumscribing Polygons and Polygonizations for Disjoint Line Segments

Authors Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, Csaba D. Tóth

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2019.9.pdf
  • Filesize: 0.92 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Combinatoric problems
Keywords
  • circumscribing polygon
  • Hamiltonicity
  • extremal combinatorics

Metrics

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

Abstract

Given a planar straight-line graph G=(V,E) in R^2, a circumscribing polygon of G is a simple polygon P whose vertex set is V, and every edge in E is either an edge or an internal diagonal of P. A circumscribing polygon is a polygonization for G if every edge in E is an edge of P.
We prove that every arrangement of n disjoint line segments in the plane has a subset of size Omega(sqrt{n}) that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to R^3.
We show that it is NP-complete to decide whether a given graph G admits a circumscribing polygon, even if G is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization.

Cite As Get BibTex

Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, and Csaba D. Tóth. Circumscribing Polygons and Polygonizations for Disjoint Line Segments. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.9

Author Details

Hugo A. Akitaya
  • Department of Computer Science, Tufts University, Medford, MA, USA
Matias Korman
  • Department of Computer Science, Tufts University, Medford, MA, USA
Mikhail Rudoy
  • CSAIL, Massachusetts Institute of Technology, Cambridge, MA, USA
  • Google Inc., Cambridge, MA, USA
Diane L. Souvaine
  • Department of Computer Science, Tufts University, Medford, MA, USA
Csaba D. Tóth
  • Department of Mathematics, California State University Northridge, Los Angeles, CA
  • Department of Computer Science, Tufts University, Medford, MA, USA

Funding

Research supported in part by the NSF awards CCF-1422311 and CCF-1423615.
  • Korman, Matias: Partially supported by MEXT KAKENHI No. 17K12635.
  • Souvaine, Diane L.: Partially supported by the Erwin Schrödinger Institute for Mathematics and Physics (ESI).

References

  1. Pankaj K. Agarwal, Ferran Hurtado, Godfried T. Toussaint, and Joan Trias. On polyhedra induced by point sets in space. Discrete Applied Mathematics, 156(1):42-54, 2008. URL: http://dx.doi.org/10.1016/j.dam.2007.08.033.
  2. Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, and Csaba D. Tóth. Circumscribing Polygons and Polygonizations. CoRR, abs/1903.07019, 2019. URL: http://arxiv.org/abs/1903.07019.
  3. Gill Barequet, Nadia Benbernou, David Charlton, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schulz, Diane L. Souvaine, Godfried T. Toussaint, and Andrew Winslow. Bounded-degree polyhedronization of point sets. Comput. Geom., 46(2):148-153, 2013. URL: http://dx.doi.org/10.1016/j.comgeo.2012.02.008.
  4. Norishige Chiba and Takao Nishizeki. The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. Journal of Algorithms, 10(2):187-211, 1989. URL: http://dx.doi.org/10.1016/0196-6774(89)90012-6.
  5. Emilio Di Giacomo and Giuseppe Liotta. The Hamiltonian Augmentation Problem and Its Applications to Graph Drawing. In Md. Saidur Rahman and Satoshi Fujita, editors, Proc. 4th International Workshop Algorithms and Computation (WALCOM), volume 5942 of LNCS, pages 35-46, Berling, 2010. Springer. URL: http://dx.doi.org/10.1007/978-3-642-11440-3_4.
  6. Alfredo García, Marc Noy, and Javier Tejel. Lower bounds on the number of crossing-free subgraphs of K_N. Comput. Geom., 16(4):211-221, 2000. URL: http://dx.doi.org/10.1016/S0925-7721(00)00010-9.
  7. Michael R. Garey, David S. Johnson, and Robert E. Tarjan. The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM J. Comput., 5(4):704-714, 1976. URL: http://dx.doi.org/10.1137/0205049.
  8. Michael Hoffmann and Csaba D. Tóth. Segment endpoint visibility graphs are Hamiltonian. Comput. Geom., 26(1):47-68, 2003. URL: http://dx.doi.org/10.1016/S0925-7721(02)00172-4.
  9. Ferran Hurtado and Csaba D. Tóth. Plane Geometric Graph Augmentation: A Generic Perspective. In János Pach, editor, Thirty Essays on Geometric Graph Theory, pages 327-354. Springer, New York, 2013. URL: http://dx.doi.org/10.1007/978-1-4614-0110-0_17.
  10. Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth. Disjoint Compatible Geometric Matchings. Discrete & Computational Geometry, 49(1):89-131, 2013. URL: http://dx.doi.org/10.1007/s00454-012-9466-9.
  11. Mashhood Ishaque, Bettina Speckmann, and Csaba D. Tóth. Shooting Permanent Rays among Disjoint Polygons in the Plane. SIAM J. Comput., 41(4):1005-1027, 2012. URL: http://dx.doi.org/10.1137/100804310.
  12. David Larman, Jiří Matoušek, János Pach, and Jenő Törőcsik. A Ramsey‐Type Result for Convex Sets. Bull. London Math. Soc., 26(2):132-136, 1994. URL: http://dx.doi.org/10.1112/blms/26.2.132.
  13. Andranik Mirzaian. Hamiltonian Triangulations and Circumscribing Polygons of Disjoint Line Segments. Comput. Geom., 2:15-30, 1992. URL: http://dx.doi.org/10.1016/0925-7721(92)90018-N.
  14. Joseph O'Rourke and Jennifer Rippel. Two Segment Classes with Hamiltonian Visibility Graphs. Comput. Geom., 4:209-218, 1994. URL: http://dx.doi.org/10.1016/0925-7721(94)90019-1.
  15. Kenta Ozeki, Nico Van Cleemput, and Carol T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts - a survey. Discrete Mathematics, 341(9):2646-2660, 2018. URL: http://dx.doi.org/10.1016/j.disc.2018.06.015.
  16. János Pach and Eduardo Rivera-Campo. On circumscribing polygons for line segments. Comput. Geom., 10(2):121-124, 1998. URL: http://dx.doi.org/10.1016/S0925-7721(97)00023-0.
  17. János Pach and Rephael Wenger. Embedding Planar Graphs at Fixed Vertex Locations. Graphs and Combinatorics, 17(4):717-728, 2001. URL: http://dx.doi.org/10.1007/PL00007258.
  18. David Rappaport. Computing simple circuits from a set of line segments is NP-complete. SIAM Journal on Computing, 18(6):1128-1139, 1989. URL: http://dx.doi.org/10.1137/0218075.
  19. David Rappaport, Hiroshi Imai, and Godfried T. Toussaint. Computing simple circuits from a set of line segments. Discrete & Computational Geometry, 5(3):289-304, 1990. URL: http://dx.doi.org/10.1007/BF02187791.
  20. Micha Sharir, Adam Sheffer, and Emo Welzl. Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn’s technique. J. Comb. Theory, Ser. A, 120(4):777-794, 2013. URL: http://dx.doi.org/10.1016/j.jcta.2013.01.002.
  21. Masatsugu Urabe and Mamoru Watanabe. On a Counterexample to a Conjecture of Mirzaian. Comput. Geom., 2:51-53, 1992. URL: http://dx.doi.org/10.1016/0925-7721(92)90020-S.
  22. Hassler Whitney. A Theorem on Graphs. Annals of Mathematics, 2nd Ser., 32(2):378-390, 1931. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »