A Time-space Trade-off for Computing the Geodesic Center of a Simple Polygon

Abstract

In this paper we study the problem of computing the geodesic center of a simple polygon when the available workspace is limited. For an $n$-vertex simple polygon, we give a time-space trade-off algorithm that finds the geodesic center in $O(T(n,s){\log }^{2}n+\frac{n^2}{s}\log n)$ expected time and uses $O(s)$ additional words of space where $s\in \Omega (\log n)\cap O(n)$, and $T(n,s)$ is the time needed for constructing the shortest path tree of a given point inside a simple polygon, in depth-first order, with $O(s)$ extra space. Applying the best current known time-space trade-off of Oh and Ahn (Algorithmica 2019) for shortest path tree, our algorithm runs in $O(\frac{n^2}{s}{\log }^{3}n)$ expected time.

11 pages