Convex hulls in polygonal domains

Luis Barba, Michael Hoffmann, Matias Korman, Alexander Pilz

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 di erent, more direct generalization of convexity, where a set X is geodesically convex if it contains all geodesics between every pair of points x, y ∈ X. The corresponding geodesic convex hull presents a few surprises, and turns out to behave quite di erently compared to the classic Euclidean setting or to the geodesic hull inside a simple polygon. We describe a class of geometric objects that su ce 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(n3h3+ε) time, for any constant ε > 0.

Original languageEnglish
Title of host publication16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018
EditorsDavid Eppstein
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages733
ISBN (Electronic)9783959770682
Publication statusPublished - 2018 Jun 1
Event16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018 - Malmo, Sweden
Duration: 2018 Jun 182018 Jun 20

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018


  • Geodesic hull
  • Phrases geometric graph
  • Polygonal domain
  • Shortest path

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Convex hulls in polygonal domains'. Together they form a unique fingerprint.

Cite this