Given n line segments in the plane, do they form the edge set of a weakly simple polygon; that is, can the segment endpoints be perturbed by at most epsilon, for any epsilon > 0, to obtain a simple polygon? While the analogous question for simple polygons can easily be answered in O(n log n) 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 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.
Reconstruction of Weakly Simple Polygons from their Edges
2016-01-01
Conference paper
Electronic Resource
English
Eigenvalues of the Laplacian on regular polygons and polygons resulting from their disection
Online Contents | 1999
|Tomographic Reconstruction of Polygons from Knot Location and Chord Length Measurements
British Library Online Contents | 1996
|Linear and Almost Linear Triangulation Algorithms for Simple Polygons
British Library Online Contents | 2005
|