A certied Delaunay graph con ict locator for semi-algebraic sets

Francesc/François Antón Castro

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review


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.
Keyword: Delaunay graph,conics,semi-algebraic sets,conflict locator
Original languageEnglish
Title of host publicationLecture Notes in Computer Science 3480
PublisherSpringer Berlin / Heidelberg
Publication date2005
Publication statusPublished - 2005
Externally publishedYes

Fingerprint Dive into the research topics of 'A certied Delaunay graph con ict locator for semi-algebraic sets'. Together they form a unique fingerprint.

Cite this