Open Collections

Voronoi diagrams of semi-algebraic sets

University of British Columbia

Most of the curves and surfaces encountered in geometric modelling are denned 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 conies 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 conies. The reduction of the Delaunay graph conflict locator for conies 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 this thesis). 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 conies, the computations get much faster by considering only the implicit equations of the generalised offsets.

Thesis/Dissertation

application/pdf

2009-11-27

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/15860

Computer Science

University of British Columbia

UBCV

DSpace