License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.10
URN: urn:nbn:de:0030-drops-67795
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6779/
Go to the corresponding LIPIcs Volume Portal

Akitaya, Hugo A. ; Tóth, Csaba D.

Reconstruction of Weakly Simple Polygons from their Edges

pdf-format:
LIPIcs-ISAAC-2016-10.pdf (0.5 MB)

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 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.

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:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6779},
  URN =		{urn:nbn:de:0030-drops-67795},
  doi =		{10.4230/LIPIcs.ISAAC.2016.10},
  annote =	{Keywords: simple polygon, line segment, geometric graph}
}

Keywords: simple polygon, line segment, geometric graph
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI