Most of the curves and surfaces encountered in geometric modelling are defined
as the set of solutions of a system of algebraic equations and inequalities (semialgebraic
sets). Many problems from different fields involve proximity queries like
finding the (nearest) neighbours or quantifying the neighbourliness of two objects.
The Voronoi diagram of a set of sites is a decomposition of space into proximal
regions. The proximal region of a site is the locus of points closer to that site
than to any other one. Voronoi diagrams allow one to answer proximity queries
after locating a query point in the Voronoi zone it belongs to. The dual graph of
the Voronoi diagram is called the Delaunay graph. Only approximations by conics
can guarantee a proper order of continuity at contact points, which is necessary for
guaranteeing the exactness of the Delaunay graph.
The theoretical purpose of this thesis is to elucidate the basic algebraic and
geometric properties of the offset to an algebraic curve and to reduce the semialgebraic
computation of the Delaunay graph to eigenvalues computations. The
practical objective of this thesis is the certified computation of the Delaunay graph
for low degree semi-algebraic sets embedded in the Euclidean plane.
The methodology combines interval analysis and computational algebraic
geometry. The central idea of this thesis is that a (one time) symbolic preprocessing
may accelerate the certified numerical evaluation of the Delaunay graph conflict
locator. The symbolic preprocessing is the computation of the implicit equation of
the generalised offset to conics. The reduction of the Delaunay graph conflict locator
for conics from a semi-algebraic problem to a linear algebra problem has been
possible through the use of the generalised Voronoi vertex (a concept introduced in
The certified numerical computation of the Delaunay graph has been possible
by using an interval analysis based library for solving zero-dimensional systems
of equations and inequalities (ALIAS). The certified computation of the Delaunay
graph relies on theorems on the uniqueness of a root in given intervals (Kantorovitch,
Moore-Krawczyk). For conics, the computations get much faster by considering only
the implicit equations of the generalised offsets.
|Number of pages
|Published - 2006