Computing a geodesic two-center of points in a simple polygon

Abstract

Given a simple polygon P with n vertices and a set Q of m points in P. we consider the geodesic k-center problem where we want to find k points, called centers, in P to minimize the maximum geodesic distance of any point of Q to its closest center. In this paper, we focus on the case of k = 2 and present an O (m(n + m) log(3) (n + m))-time algorithm for computing an optimal 2-center of Q with respect to the geodesic distance in P. (C) 2019 Elsevier B.V. All rights reserved.