The Voronoi diagram of circles made easy

François Anton; Darka Mioc; Christopher Gold

doi:10.1109/ISVD.2007.37

The Voronoi diagram of circles made easy

François Anton, Darka Mioc, Christopher Gold

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

389 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 language	English
Title of host publication	Voronoi Diagrams in Science and Engineering, 2007. ISVD '07. 4th International Symposium on
Publisher	IEEE
Publication date	2007
Pages	15-24
ISBN (Print)	0-7695-2869-4
DOIs	https://doi.org/10.1109/ISVD.2007.37
Publication status	Published - 2007
Event	4th International Symposium on Voronoi Diagrams in Science and Engineering - Glamorgan University, Pontypridd, United Kingdom Duration: 9 Jul 2007 → 11 Jul 2007 Conference number: 2007 http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4276089

Conference

Conference	4th International Symposium on Voronoi Diagrams in Science and Engineering
Number	2007
Location	Glamorgan University
Country/Territory	United Kingdom
City	Pontypridd
Period	09/07/2007 → 11/07/2007
Internet address	http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4276089

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

Access to Document

10.1109/ISVD.2007.37

AntonFinal published version, 248 KB

OpenUrl availability

Full text

Cite this

@inproceedings{6d24d3ccd58e41caba24964fe403ff02,

title = "The Voronoi diagram of circles made easy",

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.",

author = "Fran{\c c}ois Anton and Darka Mioc and Christopher Gold",

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; 4th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD'07 ; Conference date: 09-07-2007 Through 11-07-2007",

year = "2007",

doi = "10.1109/ISVD.2007.37",

language = "English",

isbn = "0-7695-2869-4",

pages = "15--24",

booktitle = "Voronoi Diagrams in Science and Engineering, 2007. ISVD '07. 4th International Symposium on",

publisher = "IEEE",

address = "United States",

url = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4276089",

}

TY - GEN

T1 - The Voronoi diagram of circles made easy

AU - Anton, François

AU - Mioc, Darka

AU - Gold, Christopher

N1 - Conference code: 2007

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

U2 - 10.1109/ISVD.2007.37

DO - 10.1109/ISVD.2007.37

M3 - Article in proceedings

SN - 0-7695-2869-4

SP - 15

EP - 24

BT - Voronoi Diagrams in Science and Engineering, 2007. ISVD '07. 4th International Symposium on

PB - IEEE

T2 - 4th International Symposium on Voronoi Diagrams in Science and Engineering

Y2 - 9 July 2007 through 11 July 2007

ER -

The Voronoi diagram of circles made easy

Abstract

Conference

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this