Facility location on a polyhedral surface (Q1434248)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Facility location on a polyhedral surface |
scientific article |
Statements
Facility location on a polyhedral surface (English)
0 references
7 July 2004
0 references
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.
0 references
facility location
0 references
1-center
0 references
polyhedral surfaces
0 references
furthest-site Voronoi diagram
0 references