A replacement for Voronoi diagrams of near linear size

For a set P of n points in R/sup d/, we define a new type of space decomposition. The new diagram provides an /spl epsi/-approximation to the distance function associated with the Voronoi diagram of P, while being of near linear size, for d/spl ges/2. This contrasts with the standard Voronoi diagram that has /spl Omega/ (n/sup [d/2]/) complexity in the worst case.