## 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 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(n^{3}h^{3+ε}) time, for any constant ε > 0.

Original language | English |
---|---|

Title of host publication | 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018 |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pages | 81-813 |

Number of pages | 733 |

Volume | 101 |

ISBN (Electronic) | 9783959770682 |

DOIs | |

Publication status | Published - 1 Jun 2018 |

Externally published | Yes |

Event | 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018 - Malmo, Sweden Duration: 18 Jun 2018 → 20 Jun 2018 |

### Conference

Conference | 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018 |
---|---|

Country/Territory | Sweden |

City | Malmo |

Period | 18/06/18 → 20/06/18 |

## Keywords

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

## ASJC Scopus subject areas

- Software