Motivation: A Voronoi diagram is a way of partitioning space which is useful in many fields, including pattern recognition, classification, machine learning, and graphics. Given a point cloud P, the Voronoi diagram of P is a set of cells, where each cell contains exactly one of the points p in P and all points in space that are closer to p than they are to any other point in P. But many of these applications deal with high-dimensional spaces, and Voronoi diagrams can have up to nd / 2 cells in d-dimensional space, which is a lot when d is large. We would like to reduce the number of cells in these Voronoi diagrams.
Goal of This Research: We would like to make approximate Voronoi diagrams which are much smaller than exact Voronoi diagrams. In particular we would like our approximate diagrams to help us quickly answer queries (questions) about approximate nearest neighbors.
Goal of This Paper: Use a (1, e)-approximate Voronoi diagram (AVD) which has small size and fast nearest neighbor querying. A (1, e)-AVD consists of cells just like a standard Voronoi diagram. Each cell contains one representative point p from the point cloud P. The difference is, a single cell now contains all points in space which are at most (1 + e) times as far from the cell's representative point p as they are from their nearest neighbor in P. Basically, such an AVD is still a partition of space, but now we do not have a separate cell for each point in P--we only need a few representative points from P to define the cells, and so each cell could contain multiple points from P. So this potentially gives us a much smaller number of cells than a standard Voronoi diagram. We can generalize and define a (t, e)-AVD as being the same as a (1, e)-AVD, except now each cell contains t representative points instead of just one. This paper gives upper and lower bounds on the size of such AVDs, and shows that such AVDs are generally much smaller than standard Voronoi diagrams.
Results: We can always construct a (1, e)-AVD in d-dimensional space with size O(n/ed). Approximate nearest neighbor queries can be answered in O(log(n/e)) time. Also, by making an assumption about what shapes cells can have, we can prove a lower bound on the size of a (1, e)-AVD and show that this assumption gives us a nearly optimally sized AVD. The results are also generalized to (t, e)-AVDs.
Motivation: Same as in the above paper.
Goal of This Research: Same as in the above paper.
Goal of This Paper: Same as in the above paper.
Results: This paper gives some tighter bounds on the space requirements for AVDs and speculates about how to improve these requirements.
Motivation: Same as in the above papers.
Goal of This Research: Same as in the above papers.
Goal of This Paper: Same as in the above papers.
Results: Using a compressed quadtree, we can bound the size of an AVD and answer approximate nearest neighbor queries in the same time as in the above papers. In two-dimensional space, the quadtree gives us a "fat triangulation" of the plane, and overlaying two fat triangulations has only linear complexity, so this is useful when we need to overlay Voronoi diagrams with other structures. Similar results hold for decomposing space into "fat simplices". Also, this paper describes an efficient solution to the problem of "point-location in equal balls" (PLEB), which is used to answer nearest neighbor queries.