Regresar

A certified delaunay graph conflict locator for semi-algebraic sets

Abstract:

Most of the curves and surfaces encountered in geometric modelling are defined as the set of common zeroes of a set of polynomials (algebraic varieties) or subsets of algebraic varieties defined by one or more algebraic inequalities (semi-algebraic sets). Many problems from different fields involve proximity queries like finding the nearest neighbour, finding all the neighbours, or quantifying the neighbourliness of two objects. The Voronoi diagram of a set of sites is a decomposition of the space into proximal regions: each site's Voronoi region is the set of points closer to that site than to any other site. The Delaunay graph of a set of sites is the dual graph of the Voronoi diagram of that set of sites, which stores the spatial adjacency relationships among sites induced by the Voronoi diagram. The Voronoi diagram has been used for solving the earlier mentioned proximity queries. The ordinary Voronoi diagram of point sites has been extended or generalised in several directions (underlying space, metrics, sites), and the resulting generalised Voronoi diagrams have found many practical applications. The Voronoi diagrams have not yet been generalised to algebraic curves or semi-algebraic sets. In this paper, we present a conflict locator for the certified incremental maintenance of the Delaunay graph of semi-algebraic sets. © Springer-Verlag Berlin Heidelberg 2005.