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

2019/08/29 by Pardis Kavand, Kavand, Pardis, Ali Mohades +3
Computer Science · Engineering · #3D Modeling in Geospatial Applications #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Robotic Path Planning Algorithms

paper · pdf · doi:10.48550/arxiv.1908.11260

openalex publication_date 2019/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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² n+ (n²)/(s) log n) expected time and uses O(s) additional words of space where s∈ Ω(log n) ∩ 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((n²)/(s) log³ n) expected time.

Related

• A linear-time algorithm for the geodesic center of a simple polygon
• The geodesic edge center of a simple polygon
• The Geodesic 2-center Problem in a Simple Polygon
• Computing the L₁ Geodesic Diameter and Center of a Simple Polygon in Linear Time
• Computing the Geodesic Centers of a Polygonal Domain