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.


    Access

    Download


    Export, share and cite



    Title :

    Reconstruction of Weakly Simple Polygons from their Edges


    Contributors:

    Publication date :

    2016-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    Self-approaching paths in simple polygons

    Bose, Prosenjit / Kostitsyna, Irina / Langerman, Stefan | BASE | 2020

    Free access

    Self-Approaching Paths in Simple Polygons

    Bose, Prosenjit / Kostitsyna, Irina / Langerman, Stefan | BASE | 2017

    Free access


    Tomographic Reconstruction of Polygons from Knot Location and Chord Length Measurements

    Belcastro, L. / Karl, W. C. / Willsky, A. S. | British Library Online Contents | 1996


    Linear and Almost Linear Triangulation Algorithms for Simple Polygons

    Dvortsov, V. I. / Ivanovskii, S. A. | British Library Online Contents | 2005