Abstract
Given an orientable genus-0 polyhedral surface defined by n triangles, and a set of m point sites} on it, we would like to identify its 1-center, i.e., the location on the surface that minimizes the maximum distance to the sites. The distance is measured as the length of the Euclidean shortest path along the surface. To compute the 1-center, we compute the furthest-site Voronoi diagram of the sites on the polyhedral surface. We show that the diagram has maximum combinatorial complexity Θ(m n 2), and present an algorithm that computes the diagram in O(m n 2log mlog n) expected time. The 1-center can then be identified in time linear in the size of the diagram.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Aronov, B., van Kreveld, M., van Oostrum, R. et al. Facility Location on a Polyhedral Surface. Discrete Comput Geom 30, 357–372 (2003). https://doi.org/10.1007/s00454-003-2769-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-003-2769-0