Home Bookmarks Papers Blog

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 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.

Abstract - Postscript, PDF.


Demo program

Some relevant pictures...


FOCS Presentation, in FOCS HTML
@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