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

    241 Downloads (Pure)

    Abstract

    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
    PublisherIEEE
    Publication date2007
    Pages15-24
    ISBN (Print)0-7695-2869-4
    DOIs
    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
    http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4276089

    Conference

    Conference4th International Symposium on Voronoi Diagrams in Science and Engineering
    Number2007
    LocationGlamorgan University
    CountryUnited Kingdom
    CityPontypridd
    Period09/07/200711/07/2007
    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

    Cite this

    Anton, F., Mioc, D., & Gold, C. (2007). The Voronoi diagram of circles made easy. In Voronoi Diagrams in Science and Engineering, 2007. ISVD '07. 4th International Symposium on (pp. 15-24). IEEE. https://doi.org/10.1109/ISVD.2007.37