Reconstruction of Weakly Simple Polygons from Their Edges

DOI10.1142/S021819591860004XzbMATH Open1397.68193arXiv1610.00361OpenAlexW3101770330MaRDI QIDQ3177902FDOQ3177902

Csaba D. Tóth, Hugo A. Akitaya

Publication date: 2 August 2018

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Triangulating a simple polygon in linear time
• Detecting Weakly Simple Polygons
• Reconstructing polygons from scanner data
• A polygon is determined by its angles
• Segment endpoint visibility graphs are Hamiltonian
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• The complexity of detecting crossingfree configurations in the plane
• On embedding a cycle in a plane graph
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Connectivity augmentation in planar straight line graphs
• On a counterexample to a conjecture of Mirzaian
• Recognizing weakly simple polygons

Cited In (4)

• Reconstructing sets of orthogonal line segments in the plane
• Title not available (Why is that?)
• Recognizing weakly simple polygons
• Reconstructing faces on a polyhedron from apparent gradients of edges

   Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Reassembling polygons from edges 👍 👎
• Reconstruction of polygons from projections 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)