Facility Location on Terrains: Extended Abstract

Boris Aronov; Marc van Kreveld; René van Oostrum; Kasturirangan Varadarajan

doi:10.1007/3-540-49381-6_4

Back

Book chapter

Facility Location on Terrains: Extended Abstract

Boris Aronov, Marc van Kreveld, René van Oostrum and Kasturirangan Varadarajan

Algorithms and Computation, pp.20-29

Lecture Notes in Computer Science, v. 1533, Springer Berlin Heidelberg

03/29/2001

DOI: 10.1007/3-540-49381-6_4

View Online

Abstract

Given a terrain defined as a piecewise-linear function with n triangles, and m point sites on it, we would like to identify the location on the terrain that minimizes the maximum distance to the sites. The distance is measured as the length of the Euclidean shortest path along the terrain. To simplify the problem somewhat, we extend the terrain to (the surface of) a polyhedron. To compute the optimum placement, we compute the furthest-site Voronoi diagram of the sites on the polyhedron. The diagram has maximum combinatorial complexity Θ(mn)2, and the algorithm runs in O(mn2 log2m(logm + logn) time.

Facility Location

Facility Location Problem

Point Site

Short Path

Voronoi Diagram

Details

Title: Subtitle: Facility Location on Terrains: Extended Abstract
Creators: Boris Aronov - New York University
Marc van Kreveld - Utrecht University
René van Oostrum - Utrecht University
Kasturirangan Varadarajan
Resource Type: Book chapter
Publication Details: Algorithms and Computation, pp.20-29
Series: Lecture Notes in Computer Science; v. 1533
DOI: 10.1007/3-540-49381-6_4
eISSN: 1611-3349
ISSN: 0302-9743
Publisher: Springer Berlin Heidelberg; Berlin, Heidelberg
Language: English
Date published: 03/29/2001
Academic Unit: Computer Science
Record Identifier: 9984259483202771

Metrics

10 Record Views