# Exact Voronoi diagram of smooth convex pseudo-circles: General predicates, and implementation for ellipses

2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We examine the problem of computing exactly the Voronoi diagram (via the dual Delaunay graph) of a set of, possibly intersecting, smooth convex \pc in the Euclidean plane, given in parametric form. Pseudo-circles are (convex) sites, every pair of which has at most two intersecting points. The Voronoi diagram is constructed incrementally. Our first contribution is to propose robust and efficient algorithms, under the exact computation paradigm, for all required predicates, thus generalizing earlier algorithms for non-intersecting ellipses. Second, we focus on \kcn, which is the hardest predicate, and express it by a simple sparse $5\times 5$ polynomial system, which allows for an efficient implementation by means of successive Sylvester resultants and a new factorization lemma. The third contribution is our \cgal-based \cpp software for the case of possibly intersecting ellipses, which is the first exact implementation for the problem. Our code spends \globaltimetext to construct the Voronoi diagram of 200 ellipses, when few degeneracies occur. It is faster than the \cgal segment Voronoi diagram, when ellipses are approximated by $k$-gons for $k>15$, and a state-of-the-art implementation of the Voronoi diagram of points, when each ellipse is approximated by more than $1250$ points.and implementation for ellipses
keyword :
Type de document :
Article dans une revue
Computer Aided Geometric Design, Elsevier, 2013, 〈10.1016/j.cagd.2013.06.005〉
Domaine :

Littérature citée [28 références]

https://hal.inria.fr/hal-00843033
Contributeur : Elias Tsigaridas <>
Soumis le : mercredi 10 juillet 2013 - 11:21:12
Dernière modification le : jeudi 11 janvier 2018 - 06:24:00
Document(s) archivé(s) le : mercredi 5 avril 2017 - 09:20:59

### Fichier

ett-vor-pcircles.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Ioannis Emiris, Elias Tsigaridas, George Tzoumas. Exact Voronoi diagram of smooth convex pseudo-circles: General predicates, and implementation for ellipses. Computer Aided Geometric Design, Elsevier, 2013, 〈10.1016/j.cagd.2013.06.005〉. 〈hal-00843033〉

### Métriques

Consultations de la notice

## 380

Téléchargements de fichiers