The furthest-site geodesic voronoi diagram

Boris Aronov, Steven Fortune, Gordon Wilfong

    Research output: Contribution to journalArticlepeer-review


    We present an O((n+k) log(n+k))-time, O(n+k)-space algorithm for computing the furthest-site Voronoi diagram of k point sites with respect to the geodesic metric within a simple n-sided polygon.

    Original languageEnglish (US)
    Pages (from-to)217-255
    Number of pages39
    JournalDiscrete & Computational Geometry
    Issue number1
    StatePublished - Dec 1993

    ASJC Scopus subject areas

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


    Dive into the research topics of 'The furthest-site geodesic voronoi diagram'. Together they form a unique fingerprint.

    Cite this