Recognizing weakly simple polygons

DOI10.4230/LIPICS.SOCG.2016.8MaRDI QIDQ3132840zbMATH OpenOpenAlexFDO

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

Publication date 30 January 2018

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

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)

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.

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

Cited in

(8)

• Reconstruction of weakly simple polygons from their edges
• Recognizing weakly simple polygons
• Embedding Graphs into Embedded Graphs
• Reconstruction of Weakly Simple Polygons from Their Edges
• Detecting weakly simple polygons
• 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)