Convex hulls in polygonal domains
OPEN ACCESS
Author / Producer
Date
2018
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Volume
101
Pages / Article No.
8
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
geometric graph; polygonal domain; geodesic hull; shortest path
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)