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.
|Title of host publication||Voronoi Diagrams in Science and Engineering, 2007. ISVD '07. 4th International Symposium on|
|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
|Conference||4th International Symposium on Voronoi Diagrams in Science and Engineering|
|Period||09/07/2007 → 11/07/2007|