Recognizing weakly simple polygons

DOI10.4230/LIPICS.SOCG.2016.8zbMATH Open1387.68230arXiv1603.07401OpenAlexW2762324796MaRDI QIDQ3132840FDOQ3132840

Hugo A. Akitaya, Jeff Erickson, Greg Aloupis, Csaba D. Tóth

Publication date: 30 January 2018

Abstract: We present an $O(nlogn)$-time algorithm that determines whether a given planar $n$-gon is weakly simple. This improves upon an $O(n^{2}logn)$-time algorithm by Chang, Erickson, and Xu (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.

Full work available at URL: https://arxiv.org/abs/1603.07401

Recommendations

• Recognizing weakly simple polygons
• Detecting weakly simple polygons
• Recognizing weakly convex visible polygons
• Reconstruction of weakly simple polygons from their edges
• Reconstruction of Weakly Simple Polygons from Their Edges
• Polygon Graph Recognition
• Characterizing and recognizing weak visibility polygons
• DETERMINING THE SEPARATION OF SIMPLE POLYGONS
• Recognizing polygons, or how to spy

zbMATH Keywords

weakly simple polygoncrossing

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Cited In (6)

• Embedding Graphs into Embedded Graphs
• Reconstruction of Weakly Simple Polygons from Their Edges
• \(c\)-planarity of embedded cyclic \(c\)-graphs
• Recognizing polygons, or how to spy
• Stability of intersections of graphs in the plane and the van Kampen obstruction
• Hanani-Tutte for approximating maps of graphs

This page was built for publication: Recognizing weakly simple polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132840)