Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/693
Approximating a voronoi cell
Authors  Arya, Sunil
Vigneron, Antoine 


Issue Date  2003  
Summary  Given a set S of n points in IR<sup>d</sup>, 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 <sub>∈</sub>(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 <sub>∈</sub>(p, S). We show that there exists a set of ∈approximate Voronoi neighbors with cardinality O(1/√∈) for d = 2 and cardinality O((1/∈)<sup>(d−1)/2</sup>log(1/∈)) for any fixed d ≥ 3. We also provide a worstcase lower bound of Ω((1/∈)<sup>(d−1)/2)</sup>) on the number of approximate Voronoi neighbors. Thus, our bound is tight in the plane and within a factor of O(log(1/∈)) from optimal in dimension d ≥ 3. Finally, based on our existence proofs, we design efficient algorithms for computing approximate Voronoi neighborhoods.  
Subjects  
Language  English 

Format  Technical report  
Access 
Files in this item:
