Journal article
Facility Location on a Polyhedral Surface
Discrete & computational geometry, Vol.30(3), pp.357-372
09/01/2003
DOI: 10.1007/s00454-003-2769-0
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 ⊖ (mn), and present an algorithm that computes the diagram in O(mn log m log n) expected time. The 1-center can then be identified in time linear in the size of the diagram.
Details
- Title: Subtitle
- Facility Location on a Polyhedral Surface
- Creators
- Boris Aronov - New York UniversityMarc van Kreveld - Utrecht UniversityRen van OostrumKasturi Varadarajan - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Discrete & computational geometry, Vol.30(3), pp.357-372
- DOI
- 10.1007/s00454-003-2769-0
- ISSN
- 0179-5376
- eISSN
- 1432-0444
- Language
- English
- Date published
- 09/01/2003
- Academic Unit
- Computer Science
- Record Identifier
- 9984259422702771
Metrics
1 Record Views