Geodesic Center of a Simple Polygon using a Logarithmic Number of Extra Variables

Abstract

In this paper, we propose an algorithm for computing the geodesic center of a simple polygon when the available workspace is limited. Our algorithm is a memory-constrained algorithm which has read-only access to the input. In addition to the input, it uses Θ(log n) words of O(log n) bits for reading and writing. The algorithm runs in O(n⁴) expected time, where n is the number of the corners of the polygon. We also show that the geodesic farthest-site Voronoi diagram of the corners of the polygon can be computed in the same time and space. As a sub-result, we present an s-workspace algorithm for finding a geodesic farthest neighbor of a given point inside a simple polygon which runs in O(n²/s) expected time where $s\in \Omega \left(\log n\right)\cap O\left(\frac{n}{\log n{\log }^5\log n}\right)$ .