Seminars

Title: Exact Delaunay graph of smooth convex pseudo-circles: General predicates, and implementation for ellipses.

Abstract: We examine the problem of computing exactly the Delaunay graph (and the dual Voronoi diagram) of a set of, possibly intersecting, smooth convex pseudo-circles in the Euclidean plane, given in parametric form. Pseudo-circles are (convex) sites, every pair of which has at most two intersecting points. The Delaunay graph is constructed incrementally. We propose exact end efficient algorithms for all required predicates. For InCircle, which is the hardest predicate, we describe a certified iterative method, which exhibits quadratic convergence and handles non-degenerate cases. We also express InCircle by a simple sparse 5x5 polynomial system, which allows for an efficient implementation by means of successive Sylvester resultants and a factorization lemma. Our C++ software for the case of ellipses is the first exact implementation for the problem, and is based on the Cgal library and its algebraic kernel. Our code spends about 1 sec per ellipse, when few degeneracies occur. It is faster than the Cgal segment Delaunay graph, when ellipses are approximated by k-gons for k > 15, and faster than the Delaunay graph of points, when they are approximated by > 240 points.

Joint work with E.Tsigaridas and G.Tzoumas.