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.
Voronoi Diagrams in Science and Engineering, 2007. Isvd '07. 4th International Symposium on, 2007, p. 15-24
Main Research Area:
Voronoi Diagrams in Science and Engineering, 2007. ISVD '07. 4th International Symposium on