1 Image Analysis and Computer Graphics, Department of Informatics and Mathematical Modeling, Technical University of Denmark2 Department of Informatics and Mathematical Modeling, Technical University of Denmark3 National Space Institute, Technical University of Denmark4 unknown
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