The complexity of bisectors and Voronoi diagrams on realistic terrains

Boris Aronov, Mark De Berg, Shripad Thite

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

    Abstract

    We prove tight bounds on the complexity of bisectors and Voronoi diagrams on so-called realistic terrains, under the geodesic distance. In particular, if n denotes the number of triangles in the terrain, we show the following two results. (i) If the triangles of the terrain have bounded slope and the projection of the set of triangles onto the xy-plane has low density, then the worst-case complexity of a bisector is Θ(n). (ii) If, in addition, the triangles have similar sizes and the domain of the terrain is a rectangle of bounded aspect ratio, then the worst-case complexity of the Voronoi diagram of m point sites is Θ(n +m√n).

    Original languageEnglish (US)
    Title of host publicationAlgorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
    Pages100-111
    Number of pages12
    DOIs
    StatePublished - 2008
    Event16th Annual European Symposium on Algorithms, ESA 2008 - Karlsruhe, Germany
    Duration: Sep 15 2008Sep 17 2008

    Publication series

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

    Other

    Other16th Annual European Symposium on Algorithms, ESA 2008
    CountryGermany
    CityKarlsruhe
    Period9/15/089/17/08

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'The complexity of bisectors and Voronoi diagrams on realistic terrains'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., De Berg, M., & Thite, S. (2008). The complexity of bisectors and Voronoi diagrams on realistic terrains. In Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings (pp. 100-111). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS). https://doi.org/10.1007/978-3-540-87744-8-9