Akitaya, Hugo A. ;
Tóth, Csaba D.
Reconstruction of Weakly Simple Polygons from their Edges
Abstract
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 NPcomplete 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 worstcase upper and lower bounds for both problems.
BibTeX  Entry
@InProceedings{akitaya_et_al:LIPIcs:2016:6779,
author = {Hugo A. Akitaya and Csaba D. T{\'o}th},
title = {{Reconstruction of Weakly Simple Polygons from their Edges}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {10:110:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6779},
URN = {urn:nbn:de:0030drops67795},
doi = {10.4230/LIPIcs.ISAAC.2016.10},
annote = {Keywords: simple polygon, line segment, geometric graph}
}
07.12.2016
Keywords: 

simple polygon, line segment, geometric graph 
Seminar: 

27th International Symposium on Algorithms and Computation (ISAAC 2016)

Issue date: 

2016 
Date of publication: 

07.12.2016 