The Voronoi diagram of circles made easy |
| | Abstract | Proximity queries among circles could be effec-
tively 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 Delau-
nay 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 eigenval-
ues of a two by two matrix. | | Keywords | Voronoi diagram, Delaunay graph, Vornoi diagram of circles, exact computation | | Type | Conference paper [With referee] | | Conference | International Symposium on Voronoi Diagrams in Science and Engineering | | Year | 2007 Month July | | Publisher | IEEE Computer Society | | Address | School of Computing, University of Glamorgan, Pontypridd, Wales, UK | | Note | Further details to come | | Electronic version(s) | [pdf] | | BibTeX data | [bibtex] | | IMM Group(s) | Scientific Computing, Image Analysis & Computer Graphics, Other |
|