1
Department of Mathematics, Faculty of Basic Sciences, Ayatollah Boroujerdi University, Boroujerd, Iran
2
Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
Abstract
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 present a time-space trade-off algorithm that finds the geodesic center in $O\!\left(T(n,s)\log^2 n+\frac{n^2}{s}\log n\right)$ expected time and uses $O(s)$ additional words of space, where $s\in\Omega(\log n)\cap O(n)$ and $T(n,s)$ denotes the time required to construct, in depth-first order, the shortest path tree of a given point inside a simple polygon using $O(s)$ extra space. Applying the time-space trade-off of Oh and Ahn (\textit{Algorithmica}, 2019) for constructing a shortest path tree yields an expected running time of $O\!\left(\frac{n^2}{s}\log^3 n\right)$.
Kavand,P , Mohades,A and Kazemi,M R . (2026). A Time-Space Trade-Off for Computing the Geodesic Center of a Simple Polygon. Journal of Applied Mathematics & Data Analytics, 2(2), 1-9.
MLA
Kavand,P , , Mohades,A , and Kazemi,M R . "A Time-Space Trade-Off for Computing the Geodesic Center of a Simple Polygon", Journal of Applied Mathematics & Data Analytics, 2, 2, 2026, 1-9.
HARVARD
Kavand P, Mohades A, Kazemi M R. (2026). 'A Time-Space Trade-Off for Computing the Geodesic Center of a Simple Polygon', Journal of Applied Mathematics & Data Analytics, 2(2), pp. 1-9.
CHICAGO
P Kavand, A Mohades and M R Kazemi, "A Time-Space Trade-Off for Computing the Geodesic Center of a Simple Polygon," Journal of Applied Mathematics & Data Analytics, 2 2 (2026): 1-9,
VANCOUVER
Kavand P, Mohades A, Kazemi M R. A Time-Space Trade-Off for Computing the Geodesic Center of a Simple Polygon. JAMDA. 2026;2(2):1-9.
