A lower bound on Voronoi diagram complexity

Boris Aronov

    Research output: Contribution to journalArticle

    Abstract

    A lower bound on Voronoi diagram complexity is presented. The Voronoi diagram is a classification of points of the ambient space according to the identity of the closest site or sites. Results provided evidence that the bound derived from envelope analysis is closer to the truth as the conjecture of Sharir does not hold.

    Original languageEnglish (US)
    Pages (from-to)183-185
    Number of pages3
    JournalInformation Processing Letters
    Volume83
    Issue number4
    DOIs
    StatePublished - Aug 31 2002

    Keywords

    • Computational complexity
    • Computational geometry
    • Voronoi diagram

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Signal Processing
    • Information Systems
    • Computer Science Applications

    Fingerprint Dive into the research topics of 'A lower bound on Voronoi diagram complexity'. Together they form a unique fingerprint.

  • Cite this