Facility Location on a Polyhedral Surface |
| |
Authors: | Aronov Boris van Kreveld Marc van Oostrum René Varadarajan Kasturi |
| |
Institution: | (1) Department of Computer and Information Science, Polytechnic University, Brooklyn, NY 11201-3840, USA;(2) Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands;(3) Department of Computer Science, University of Iowa, IA 52240, USA |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|