Reconstruction of Weakly Simple Polygons from Their Edges

DOI10.1142/S021819591860004XMaRDI QIDQ3177902zbMATH OpenOpenAlexFDO

Authors Hugo A. Akitaya, Csaba D. Tóth

Publication date 2 August 2018

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

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

zbMATH Keywords

simple polygonEuler tourline segment

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Given $n$ line segments in the plane, do they form the edge set of a emph{weakly simple polygon}; that is, can the segment endpoints be perturbed by at most $varepsilon$, for any $varepsilon>0$, to obtain a simple polygon? While the analogous question for emph{simple polygons} can easily be answered in $O(nlogn)$ time, we show that it is NP-complete for weakly simple polygons. We give $O(n)$-time algorithms in two special cases: when all segments are collinear, or the segment endpoints are in general position. These results extend to the variant in which the segments are emph{directed}, and the counterclockwise traversal of a polygon should follow the orientation. We study related problems for the case that the union of the $n$ input segments is connected. (i) If each segment can be subdivided into several segments, find the minimum number of subdivision points to form a weakly simple polygon. (ii) If new line segments can be added, find the minimum total length of new segments that creates a weakly simple polygon. We give worst-case upper and lower bounds for both problems.

Recommendations

• Reconstruction of weakly simple polygons from their edges
• scientific article; zbMATH DE number 8793
• Reassembling polygons from edges
• Reconstruction of polygons from projections
• scientific article; zbMATH DE number 1953195
• scientific article; zbMATH DE number 1538125
• Detecting weakly simple polygons
• Recognizing weakly simple polygons
• Recognizing weakly simple polygons
• Reconstructing convex polygons and convex polyhedra from edge and face counts in orthogonal projections

Cites work

• scientific article; zbMATH DE number 4062601 (Why is no real title available?)
• scientific article; zbMATH DE number 8793 (Why is no real title available?)
• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• A polygon is determined by its angles
• Computational geometry. Algorithms and applications.
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Connectivity augmentation in planar straight line graphs
• Detecting weakly simple polygons
• On a counterexample to a conjecture of Mirzaian
• On embedding a cycle in a plane graph
• Optimal binary space partitions for segments in the plane
• Recognizing weakly simple polygons
• Reconstructing polygons from scanner data
• Segment endpoint visibility graphs are Hamiltonian
• The complexity of detecting crossingfree configurations in the plane
• Triangulating a simple polygon in linear time

Cited in

(8)

• scientific article; zbMATH DE number 637329 (Why is no real title available?)
• Detecting weakly simple polygons
• Reconstructing a simple polygon from its angles
• Reconstruction of weakly simple polygons from their edges
• Recognizing weakly simple polygons
• Recognizing weakly simple polygons
• Reconstructing sets of orthogonal line segments in the plane
• Reconstructing faces on a polyhedron from apparent gradients of edges

This page was built for publication: Reconstruction of Weakly Simple Polygons from Their Edges

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