The Voronoi diagram of circles made easy

François Anton, Darka Mioc, Christopher Gold

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    370 Downloads (Pure)


    Proximity queries among circles could be effectively answered if the Delaunay graph for sets of circles could be computed in an efficient and exact way. In this paper, we first show a necessary and sufficient condition of connectivity of the Voronoi diagram of circles. Then, we show how the Delaunay graph of circles (the dual graph of the Voronoi diagram of circles) can be computed exactly, and in a much simpler way, by computing the eigenvalues of a two by two matrix.
    Original languageEnglish
    Title of host publicationVoronoi Diagrams in Science and Engineering, 2007. ISVD '07. 4th International Symposium on
    Publication date2007
    ISBN (Print)0-7695-2869-4
    Publication statusPublished - 2007
    Event4th International Symposium on Voronoi Diagrams in Science and Engineering - Glamorgan University, Pontypridd, United Kingdom
    Duration: 9 Jul 200711 Jul 2007
    Conference number: 2007


    Conference4th International Symposium on Voronoi Diagrams in Science and Engineering
    LocationGlamorgan University
    Country/TerritoryUnited Kingdom
    Internet address

    Bibliographical note

    Copyright: 2007 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE


    Dive into the research topics of 'The Voronoi diagram of circles made easy'. Together they form a unique fingerprint.

    Cite this