TY - GEN
T1 - Facility location on terrains
AU - Aronov, Boris
AU - Van Kreveld, Marc
AU - Van Oostrum, René
AU - Varadarajan, Kasturirangan
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 -