Exact computation of the Voronoi Diagram of spheres in 3D, its topology and its geometric invariants

François Anton, Darka Mioc, Marcelo Santos

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

318 Downloads (Pure)

Abstract

In this paper, we are addressing the exact computation of the Delaunay graph (or quasi-triangulation) and the Voronoi diagram of spheres using Wu’s algorithm. Our main contribution is first a methodology for automated derivation of invariants of the Delaunay empty circumcircle predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are following Wu’s algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu’s algorithm on the invariants.
Original languageEnglish
Title of host publicationProceedings of the 8th ISVD International Symposium on Voronoi Diagrams in Science and Engineering
Place of PublicationChina
Publication date2011
Pages58-66
ISBN (Print)978-1-4577-1026-1
DOIs
Publication statusPublished - 2011
Event8th International Symposium on Voronoi Diagrams in Science and Engineering - Qingdao, China
Duration: 28 Jun 201130 Jun 2011
Conference number: 8
http://informatik.uni-trier.de/~ley/db/conf/isvd/isvd2011.html

Conference

Conference8th International Symposium on Voronoi Diagrams in Science and Engineering
Number8
CountryChina
CityQingdao
Period28/06/201130/06/2011
Internet address

Cite this

Anton, F., Mioc, D., & Santos, M. (2011). Exact computation of the Voronoi Diagram of spheres in 3D, its topology and its geometric invariants. In Proceedings of the 8th ISVD International Symposium on Voronoi Diagrams in Science and Engineering (pp. 58-66). China. https://doi.org/10.1109/ISVD.2011.16