ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

AnO(n logn) plane-sweep algorithm forL 1 andL ∞ Delaunay triangulations (1991)

Shute, Gary M. ; Deneen, Linda L. ; Thomborson, Clark D.

Springer

Algorithmica 6 (1991), S. 207-221

add to mindlist on the mindlist

Details

ISSN: 1432-0541

Keywords: Delaunay triangulation ; Plane-sweep algorithm ; Voronoi diagram ; L 1 metric ; L ∞ metric ; Computational geometry ; Minimal spanning tree

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract TheDelaunay diagram on a set of points in the plane, calledsites, is the straight-line dual graph of the Voronoi diagram. When no degeneracies are present, the Delaunay diagram is a triangulation of the sites, called theDelaunay triangulation. When degeneracies are present, edges must be added to the Delaunay diagram to obtain a Delaunay triangulation. In this paper we describe an optimalO(n logn) plane-sweep algorithm for computing a Delaunay triangulation on a possibly degenerate set of sites in the plane under theL 1 metric or theL ∞ metric.

Type of Medium: Electronic Resource

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

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit