A Replacement for Voronoi
Diagrams of Near Linear Size

Sariel Har-Peled

The journal version is here.
For a set P of n points in R^{d},
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"
}

Last modified: Thu Jan 12 18:48:17 CST 2012
Last updated: Mon May 21 11:25:35 CDT 2001