A lower bound on Voronoi diagram complexity

Boris Aronov

    Research output: Contribution to journalArticlepeer-review


    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
    Issue number4
    StatePublished - Aug 31 2002


    • Computational complexity
    • Computational geometry
    • Voronoi diagram

    ASJC Scopus subject areas

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


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

    Cite this