TY - GEN

T1 - Facility location on terrains

AU - Aronov, Boris

AU - Van Kreveld, Marc

AU - Van Oostrum, René

AU - Varadarajan, Kasturirangan

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1998

Y1 - 1998

N2 - 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 θ(mn2), and the algorithm runs in O(mn2 log 2 m(logm + logn)) time.

AB - 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 θ(mn2), and the algorithm runs in O(mn2 log 2 m(logm + logn)) time.

UR - http://www.scopus.com/inward/record.url?scp=84867478123&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867478123&partnerID=8YFLogxK

U2 - 10.1007/3-540-49381-6_4

DO - 10.1007/3-540-49381-6_4

M3 - Conference contribution

AN - SCOPUS:84867478123

SN - 3540653856

SN - 9783540653851

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 19

EP - 29

BT - Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings

PB - Springer Verlag

T2 - 9th Annual International Symposium on Algorithms and Computation, ISAAC'98

Y2 - 14 December 1998 through 16 December 1998

ER -