Facility Location on a Polyhedral Surface

被引：0

作者：

Boris Aronov

Marc van Kreveld

René van Oostrum

Kasturi Varadarajan

机构：

[1] Department of Computer and Information Science,

[2] Polytechnic University,undefined

[3] Brooklyn,undefined

[4] NY 11201-3840,undefined

[5] Institute of Information and Computing Sciences,undefined

[6] Utrecht University,undefined

[7] P.O. Box 80.089,undefined

[8] 3508 TB Utrecht,undefined

[9] Department of Computer Science,undefined

[10] University of Iowa,undefined

[11] IA 52240,undefined

来源：

Discrete & Computational Geometry | 2003年 / 30卷

关键词：

Short Path; Maximum Distance; Time Linear; Facility Location; Voronoi Diagram;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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 Θ(mn2), and present an algorithm that computes the diagram in O(mn2log mlog n) expected time. The 1-center can then be identified in time linear in the size of the diagram.

引用

页码：357 / 372

页数：15