On the geodesic voronoi diagram of point sites in a simple polygon

Boris Aronov

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Given a simple polygon with n sides in the plane and a set of k point "sites" in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal "geodesic" distance inside the polygon as the metric. We describe an O((n + k) log(n + k) log n)-time algorithm for solving this problem and sketch a faster O((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.

    Original languageEnglish (US)
    Pages (from-to)109-140
    Number of pages32
    JournalAlgorithmica
    Volume4
    Issue number1
    DOIs
    StatePublished - Dec 1989

    Keywords

    • Computational geometry
    • Geodesic metric
    • Shortest paths
    • Simple polygons
    • Voronoi diagrams

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics

    Fingerprint

    Dive into the research topics of 'On the geodesic voronoi diagram of point sites in a simple polygon'. Together they form a unique fingerprint.

    Cite this