Approximating a voronoi cell
Sunil Arya, Antoine Vigneron · 2003
called sites, we consider the problem of approximating the Voronoi cell of a site p by a convex polyhedron with a small number of facets or, equivalently, of finding a small set of approximate Voronoi neighbors of p. More precisely, we define an -approximate Voronoi neighborhood of p, denoted AVN (p; S), to be a subset of S satisfying the following property: p is an -approximate nearest neighbor for any point q inside the convex polyhedron defined by the bisectors between p and the sites in AVN (p; S).