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."}
   author = "S.~{Har-Peled}",
   title = "A Replacement for Voronoi Diagrams of Near Linear
   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