Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Barba, Luis; Hoffmann, Michael; Korman, Matias; Pilz, Alexander http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-88343
URL:

; ; ;

Convex Hulls in Polygonal Domains

pdf-format:


Abstract

We study generalizations of convex hulls to polygonal domains with holes. Convexity in Euclidean space is based on the notion of shortest paths, which are straight-line segments. In a polygonal domain, shortest paths are polygonal paths called geodesics. One possible generalization of convex hulls is based on the "rubber band" conception of the convex hull boundary as a shortest curve that encloses a given set of sites. However, it is NP-hard to compute such a curve in a general polygonal domain. Hence, we focus on a different, more direct generalization of convexity, where a set X is geodesically convex if it contains all geodesics between every pair of points x,y in X. The corresponding geodesic convex hull presents a few surprises, and turns out to behave quite differently compared to the classic Euclidean setting or to the geodesic hull inside a simple polygon. We describe a class of geometric objects that suffice to represent geodesic convex hulls of sets of sites, and characterize which such domains are geodesically convex. Using such a representation we present an algorithm to construct the geodesic convex hull of a set of O(n) sites in a polygonal domain with a total of n vertices and h holes in O(n^3h^{3+epsilon}) time, for any constant epsilon > 0.

BibTeX - Entry

@InProceedings{barba_et_al:LIPIcs:2018:8834,
  author =	{Luis Barba and Michael Hoffmann and Matias Korman and Alexander Pilz},
  title =	{{Convex Hulls in Polygonal Domains}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8834},
  URN =		{urn:nbn:de:0030-drops-88343},
  doi =		{10.4230/LIPIcs.SWAT.2018.8},
  annote =	{Keywords: geometric graph, polygonal domain, geodesic hull, shortest path}
}

Keywords: geometric graph, polygonal domain, geodesic hull, shortest path
Seminar: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue date: 2018
Date of publication: 2018


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