LIPIcs.SoCG.2016.8.pdf
- Filesize: 0.76 MB
- 16 pages
Document
Recognizing Weakly Simple Polygons
Authors
-
Part of:
Volume:
32nd International Symposium on Computational Geometry (SoCG 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-10
Cite As Get BibTex
Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba Tóth. Recognizing Weakly Simple Polygons. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.8
Abstract
We present an O(n log n)-time algorithm that determines whether a given planar n-gon is weakly simple. This improves upon an O(n^2 log n)-time algorithm by [Chang, Erickson, and Xu, SODA, 2015]. Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question.
Subject Classification
Keywords
- weakly simple polygon
- crossing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba D. Tóth. Recognizing weakly simple polygons. Preprint, 2016. URL: http://arxiv.org/abs/1603.07401.
-
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S.B. Mitchell, Saurabh Sethia, and Steven S. Skiena. When can you fold a map? Computational Geometry, 29(1):23-46, 2004.
-
Marshall Bern and Barry Hayes. The complexity of flat origami. In Proc. 7th ACM-SIAM Sympos. on Discrete Algorithms, pages 175-183, 1996.
-
Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Proc. 26th ACM-SIAM Sympos. on Discrete Algorithms, pages 1655-1670, 2015.
-
Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6(3):485-524, 1991.
-
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.
-
Ares Ribó Mor. Realization and counting problems for planar structures. PhD thesis, Freie Universität Berlin, Department of Mathematics and Computer Science, 2006.
-
Michael Ian Shamos and Dan Hoey. Geometric intersection problems. In Proc. 17th IEEE Sympos. Foundations of Computer Science, pages 208-215, 1976.