Facility Location on a Polyhedral Surface

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

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Given an orientable genus-0 polyhedral surface defined by n triangles, and a set of m point sites on it, we would like to identify its 1-center, i.e., the location on the surface that minimizes the maximum distance to the sites. The distance is measured as the length of the Euclidean shortest path along the surface. To compute the 1-center, we compute the furthest-site Voronoi diagram of the sites on the polyhedral surface. We show that the diagram has maximum combinatorial complexity ⊖ (mn), and present an algorithm that computes the diagram in O(mn log m log n) expected time. The 1-center can then be identified in time linear in the size of the diagram.

    Original languageEnglish (US)
    Pages (from-to)357-372
    Number of pages16
    JournalDiscrete and Computational Geometry
    Volume30
    Issue number3
    DOIs
    StatePublished - Oct 2003

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics

    Fingerprint

    Dive into the research topics of 'Facility Location on a Polyhedral Surface'. Together they form a unique fingerprint.

    Cite this