Document Open Access Logo

Reconstruction of Weakly Simple Polygons from their Edges

Authors Hugo A. Akitaya, Csaba D. Tóth

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2016.10.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • simple polygon
  • line segment
  • geometric graph

Metrics

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

Abstract

Given n line segments in the plane, do they form the edge set of a weakly simple polygon; that is, can the segment endpoints be perturbed by at most epsilon, for any epsilon > 0, to obtain a simple polygon? While the analogous question for simple polygons can easily be answered in O(n log n) time, we show that it is NP-complete for weakly simple polygons. We give O(n)-time algorithms in two special cases: when all segments are collinear, or the segment endpoints are in general position. These results extend to the variant in which the segments are directed, and the counterclockwise traversal of a polygon should follow the orientation.

We study related problems for the case that the union of the n input segments is connected. (i) If each segment can be subdivided into several segments, find the minimum number of subdivision points to form a weakly simple polygon. (ii) If new line segments can be added, find the minimum total length of new segments that creates a weakly simple polygon. We give worst-case upper and lower bounds for both problems.

Cite As Get BibTex

Hugo A. Akitaya and Csaba D. Tóth. Reconstruction of Weakly Simple Polygons from their Edges. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.10

Author Details

Hugo A. Akitaya
Csaba D. Tóth

References

  1. Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba Tóth. Recognizing weakly simple polygons. In Proc. 32nd Int. Sympos. Comput. Geom., volume 51 of LIPIcs, Dagstuhl, 2016. Google Scholar
  2. Hugo A. Akitaya and Csaba D. Tóth. Reconstruction of weakly simple polygons from theirs edges. Preprint, arXiv, 2016. Google Scholar
  3. Gill Barequet, Craig Gotsman, and Avishay Sidlesky. Polygon reconstruction from line cross-sections. In Proc. 18th Canadian Conf. Comput. Geom., Kingston, ON, 2006. Google Scholar
  4. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 3rd edition, 2008. Google Scholar
  5. Mark de Berg and Amirali Khosravi. Optimal binary space partitions in the plane. Internat. J. Comput. Geom. Appl., 22(3):187-205, 2012. Google Scholar
  6. Therese Biedl, Stephane Durocher, and Jack Snoeyink. Reconstructing polygons from scanner data. Theoret. Comput. Sci., 412(32):4161-4172, 2011. Google Scholar
  7. Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pages 1655-1670. SIAM, 2015. Google Scholar
  8. Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6(3):485-524, 1991. Google Scholar
  9. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, and Maurizio Pizzonia. On embedding a cycle in a plane graph. Discrete Math., 309(7):1856-1869, 2009. Google Scholar
  10. Andreas Darmann, Janosch Döcker, and Britta Dorn. On planar variants of the monotone satisfiability problem with bounded variable appearances. Preprint, arXiv:1604.05588, 2016. Google Scholar
  11. Yann Disser, Matúš Mihalák, and Peter Widmayer. A polygon is determined by its angles. Comput. Geom. Theory Appl., 44(8):418-426, 2011. Google Scholar
  12. Michael Formann and Gerhard J. Woeginger. On the reconstruction of simple polygons. Bulletin EATCS, 40:225-230, 1990. Google Scholar
  13. Carl Hierholzer and Chr Wiener. Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6(1):30-32, 1873. Google Scholar
  14. Michael Hoffmann and Csaba D Tóth. Segment endpoint visibility graphs are Hamiltonian. Comput. Geom. Theory Appl., 26(1):47-68, 2003. Google Scholar
  15. Klaus Jansen and Gerhard J Woeginger. The complexity of detecting crossingfree configurations in the plane. BIT Numerical Mathematics, 33(4):580-595, 1993. Google Scholar
  16. Joseph O’Rourke. Uniqueness of orthogonal connect-the-dots. In Godfried T. Tousaint, editor, Computational Morphology, pages 97-104. North-Holland, 1988. Google Scholar
  17. David Rappaport. Computing simple circuits from a set of line segments is NP-complete. SIAM J. Comput., 18(6):1128-1139, 1989. Google Scholar
  18. Csaba D Tóth. Connectivity augmentation in planar straight line graphs. European J. Combin., 33(3):408-425, 2012. Google Scholar
  19. Masatsugu Urabe and Mamoru Watanabe. On a counterexample to a conjecture of Mirzaian. Comput. Geom. Theory Appl., 2(1):51-53, 1992. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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