### 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(mn^{2} log ^{2} m(logm + logn)) time.

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings |

Publisher | Springer Verlag |

Pages | 19-29 |

Number of pages | 11 |

ISBN (Print) | 3540653856, 9783540653851 |

DOIs | |

State | Published - 1998 |

Event | 9th Annual International Symposium on Algorithms and Computation, ISAAC'98 - Taejon, Korea, Republic of Duration: Dec 14 1998 → Dec 16 1998 |

### Publication series

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

Volume | 1533 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

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

Country | Korea, Republic of |

City | Taejon |

Period | 12/14/98 → 12/16/98 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Facility location on terrains'. Together they form a unique fingerprint.

## Cite this

*Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings*(pp. 19-29). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1533 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-49381-6_4