2026-08-18T05:40:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6779 2024-03-06T10:38:52Z ddc:004 open_access

Reconstruction of Weakly Simple Polygons from their Edges Akitaya, Hugo A. Tóth, Csaba D. simple polygon line segment geometric graph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo A. Akitaya and Csaba D. Tóth 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.10 urn:nbn:de:0030-drops-67795 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.10 eng https://creativecommons.org/licenses/by/3.0/legalcode