Facility location on terrains

Boris Aronov, Marc Van Kreveld, René Van Oostrum, Kasturirangan Varadarajan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings
    PublisherSpringer Verlag
    Pages19-29
    Number of pages11
    ISBN (Print)3540653856, 9783540653851
    DOIs
    StatePublished - 1998
    Event9th Annual International Symposium on Algorithms and Computation, ISAAC'98 - Taejon, Korea, Republic of
    Duration: Dec 14 1998Dec 16 1998

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume1533 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other9th Annual International Symposium on Algorithms and Computation, ISAAC'98
    Country/TerritoryKorea, Republic of
    CityTaejon
    Period12/14/9812/16/98

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

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

    Cite this