Facility location on a polyhedral surface (Q1434248)

This paper considers the Euclidean 1-center problem on a polyhedral surface: Given an orientable genus-0 polyhedral 2-surface defined by \(n\) triangles, and a set of \(m\) sites on it, identify a location on the surface that minimizes the maximum geodesic distance to the sites. For this purpose, the furthest-site Voronoi diagram is studied; it turns out to have a worst-case combinatorial complexity of \(\Theta(mn^2)\). The resulting algorithm for computing the diagram has complexity \(O(mn^2\log m \log n)\), and the 1-center can be determined in time linear in the size of the diagram.