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 straightline 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 NPhard 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:18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8834},
URN = {urn:nbn:de:0030drops88343},
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 
Collection: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 