Computing the Geodesic Centers of a Polygonal Domain
classification
💻 cs.CG
keywords
polygonalalgorithmdomainepsilongeodesicgiveninputtime
pith:UAXRNH3N Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{UAXRNH3N}
Prints a linked pith:UAXRNH3N badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.