ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Randomized incremental construction of Delaunay and Voronoi diagrams (1992)

Guibas, Leonidas J. ; Knuth, Donald E. ; Sharir, Micha

Springer

Algorithmica 7 (1992), S. 381-413

add to mindlist on the mindlist

Details

ISSN: 1432-0541

Keywords: Delaunay triangulation ; Voronoi diagram ; randomized algorithms

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract In this paper we give a new randomized incremental algorithm for the construction of planar Voronoi diagrams and Delaunay triangulations. The new algorithm is more “on-line” than earlier similar methods, takes expected timeO(nℝgn) and spaceO(n), and is eminently practical to implement. The analysis of the algorithm is also interesting in its own right and can serve as a model for many similar questions in both two and three dimensions. Finally we demonstrate how this approach for constructing Voronoi diagrams obviates the need for building a separate point-location structure for nearest-neighbor queries.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01758770

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit