Recognizing weakly simple polygons

DOI10.1007/S00454-017-9918-3MaRDI QIDQ1688854zbMATH OpenOpenAlexFDO

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

Publication date 11 January 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/5900/

zbMATH Keywords

perturbationsimple polygoncombinatorial embedding

Mathematics Subject Classification ID

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

Recommendations

• Recognizing weakly simple polygons
• Detecting weakly simple polygons
• Reconstruction of weakly simple polygons from their edges
• Linear-time algorithms for weakly-monotone polygons
• Reconstruction of Weakly Simple Polygons from Their Edges

Cites work

• scientific article; zbMATH DE number 1947389 (Why is no real title available?)
• scientific article; zbMATH DE number 1498604 (Why is no real title available?)
• scientific article; zbMATH DE number 1877249 (Why is no real title available?)
• scientific article; zbMATH DE number 871913 (Why is no real title available?)
• A Census of Plane Graphs with Polyline Edges
• Computational geometry. Algorithms and applications.
• Detecting weakly simple polygons
• Dynamic LCA Queries on Trees
• Flat foldings of plane graphs with prescribed angles and edge lengths
• On approximability by embeddings of cycles in the plane.
• On embedding a cycle in a plane graph
• Polygons: Meister was right and Poinsot was wrong but prevailed
• Triangulating a simple polygon in linear time
• When can you fold a map?

Cited in

(14)

• Detecting weakly simple polygons
• Crossing minimization in perturbed drawings
• Crossing minimization in perturbed drawings
• Piercing pairwise intersecting geodesic disks
• Reconstruction of weakly simple polygons from their edges
• Atomic Embeddability, Clustered Planarity, and Thickenability
• Recognizing weakly simple polygons
• Finding weakly simple closed quasigeodesics on polyhedral spheres
• Reconstruction of Weakly Simple Polygons from Their Edges
• Linear-time algorithms for weakly-monotone polygons
• A linear time algorithm to remove winding of a simple polygon
• Embedding graphs into embedded graphs
• Minimum Cuts in Surface Graphs
• Recognizing polygons, or how to spy

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 Q1688854)