Voronoi Diagrams of Algebraic Distance Fields

Ioannis Z. Emiris 1 Angelos Mantzaflaris 2, 3, * Bernard Mourrain 2
* Corresponding author
2 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : We design and implement an efficient and certified algorithm for the computation of Voronoi Diagrams (VD's) constrained to a given domain. Our framework is general and applicable to any VD-type where the distance field is given explicitly or implicitly by a polynomial, notably the anisotropic VD or VD's of non-punctual sites. We use the Bernstein form of polynomials and DeCasteljau's algorithm to subdivide the initial domain and isolate bisector, or domains that contain a Voronoi vertex. The efficiency of our algorithm is due to a filtering process, based on bounding the field over the subdivided domains. This allows to exclude functions (thus sites) that do not contribute locally to the lower envelope of the lifted diagram. The output is a polygonal description of each Voronoi cell, within any user-defined precision, isotopic to the exact VD. Correctness of the result is implied by the certified approximations of bisector branches, which are computed by existing methods for handling algebraic curves. First experiments with our C++ implementation, based on double precision arithmetic, demonstrate the adaptability of the algorithm.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download


https://hal.inria.fr/hal-00722406
Contributor : Angelos Mantzaflaris <>
Submitted on : Wednesday, August 1, 2012 - 3:58:33 PM
Last modification on : Wednesday, October 17, 2018 - 5:02:04 PM
Long-term archiving on : Friday, December 16, 2016 - 4:31:57 AM

Files

voronoi_diagrams_CAD2012.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Ioannis Z. Emiris, Angelos Mantzaflaris, Bernard Mourrain. Voronoi Diagrams of Algebraic Distance Fields. Computer-Aided Design, Elsevier, 2013, 45 (2), pp.511-516. ⟨10.1016/j.cad.2012.10.043⟩. ⟨hal-00722406⟩

Share

Metrics

Record views

710

Files downloads

639