|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/693
|
| Title: | Approximating a voronoi cell |
| Authors: | Arya, Sunil
Vigneron, Antoine |
| Keywords: | Approximation
Voronoi neighbors |
| Issue Date: | 2003 |
| Series/Report no.: | HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2003-10 |
| Abstract: | Given a set S of n points in IRd, 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).
We show that there exists a set of ∈-approximate Voronoi neighbors with cardinality O(1/√∈) for d = 2 and cardinality O((1/∈)(d−1)/2log(1/∈)) for any fixed d ≥ 3. We also provide a worst-case lower bound of Ω((1/∈)(d−1)/2)) 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. |
| URI: | http://hdl.handle.net/1783.1/693 |
| Appears in Collections: | CSE TCSC Research Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| 200310.pdf | | 162Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
