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

Article type: Research Article

Authors: Kavand, P. | Mohades, A.^{; *}

Affiliations: Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran. kavandpardis@aut.ac.ir, Mohades@aut.ac.ir

Correspondence: [*] Address for correspondence: Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran.

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(n4) 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(n2/s) expected time where s∈Ω(logn)∩O(nlogn log5logn).

Keywords: Computational geometry, memory-constrained algorithms, geodesic center, geodesic farthest neighbor, geodesic farthest-site Voronoi diagram

DOI: 10.3233/FI-2019-1844

Journal: Fundamenta Informaticae, vol. 169, no. 3, pp. 211-235, 2019