Computing the Geodesic Centers of a Polygonal Domain
Preprint
Abstract
We present an algorithm that computes the geodesic center of a given polygonal domain. The running time of our algorithm is $O(n^{12+\epsilon})$ for any $\epsilon>0$, where $n$ is the number of corners of the input polygonal domain. Prior to our work, only the very special case where a simple polygon is given as input has been intensively studied in the 1980s, and an $O(n \log n)$-time algorithm is known by Pollack et al. Our algorithm is the first one that can handle general polygonal domains having one or more polygonal holes.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- The Geodesic Diameter of Polygonal DomainsDiscrete & Computational Geometry, 2013
- An Optimal Algorithm for Euclidean Shortest Paths in the PlaneSIAM Journal on Computing, 1999
- Matrix Searching with the Shortest-Path MetricSIAM Journal on Computing, 1997
- Almost tight upper bounds for lower envelopes in higher dimensionsDiscrete & Computational Geometry, 1994
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrainsDiscrete & Computational Geometry, 1994
- Computing the geodesic center of a simple polygonDiscrete & Computational Geometry, 1989
- Computing geodesic furthest neighbors in simple polygonsJournal of Computer and System Sciences, 1989
- Computing the Geodesic Center of a Simple Polygon1987