Conference paper
The Voronoi diagram of circles made easy
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.
| Language: | English |
|---|---|
| Publisher: | IEEE |
| Year: | 2007 |
| Pages: | 15-24 |
| Proceedings: | 4th International Symposium on Voronoi Diagrams in Science and Engineering |
| ISBN: | 0769528694 and 9780769528694 |
| Types: | Conference paper |
| DOI: | 10.1109/ISVD.2007.37 |
| ORCIDs: | Anton, François |
Data structures Delaunay graph Eigenvalues and eigenfunctions Euclidean distance Geodesy Geophysics computing Gold Informatics Mathematical model Sufficient conditions Testing Voronoi diagram circles computational geometry dual graph eigenvalues eigenvalues and eigenfunctions graph theory proximity queries
