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

Boris Aronov

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

    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 )log2(n+k)) time algorithm for solving this problem and sketch a faster 0((n+t)log(n+k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987
    EditorsD. Soule
    PublisherAssociation for Computing Machinery, Inc
    Pages39-49
    Number of pages11
    ISBN (Electronic)0897912314, 9780897912310
    DOIs
    StatePublished - Oct 1 1987
    Event3rd Annual Symposium on Computational Geometry, SCG 1987 - Waterloo, Canada
    Duration: Jun 8 1987Jun 10 1987

    Publication series

    NameProceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987

    Other

    Other3rd Annual Symposium on Computational Geometry, SCG 1987
    CountryCanada
    CityWaterloo
    Period6/8/876/10/87

    ASJC Scopus subject areas

    • Geometry and Topology
    • Computational 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

    Aronov, B. (1987). On the geodesic Voronoi diagram of point sites in a simple polygon. In D. Soule (Ed.), Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 (pp. 39-49). (Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987). Association for Computing Machinery, Inc. https://doi.org/10.1145/41958.41963