A Replacement for Voronoi
Diagrams of Near Linear Size
Sariel Har-Peled
For a set P of n points in Rd,
we define a new type of space decomposition. The new diagram
provides an µ-approximation to the distance function
associated with the Voronoi diagram of P, while being
of near linear size, for d >= 2. This contrasts with the
standard Voronoi diagram that has Omega( n[d/2])
complexity in the worst case.
@string{FOCS_2001 = "Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci."}
@inproceedings{h-rvdnl-01,
author = "S.~{Har-Peled}",
title = "A Replacement for Voronoi Diagrams of Near Linear
Size",
booktitle = FOCS_2001,
year = 2001,
pages = "94--103"
}