2026-07-20T14:48:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5900 2024-03-06T10:37:14Z ddc:004 open_access

Recognizing Weakly Simple Polygons Akitaya, Hugo A. Aloupis, Greg Erickson, Jeff Tóth, Csaba weakly simple polygon crossing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo A. Akitaya and Greg Aloupis and Jeff Erickson and Csaba Tóth 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.8 urn:nbn:de:0030-drops-59003 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.8 eng https://creativecommons.org/licenses/by/3.0/legalcode