TY - JOUR T1 - The ABCs of AVDs: Geometric Retrieval Made Simple JF - Algorithms and Computation Y1 - 2005 A1 - Mount, Dave AB - One of the best known structures in computational geometry is the Voronoi diagram. Given a set of n points in space, called sites, this is a subdivision that partitions space into n convex cells according which site is closest. The Voronoi diagram and its dual, the Delaunay triangulation are among the most fundamental proximity structures known, and have numerous uses in science. For example, applying point location to the subdivision defined by a Voronoi diagram answers nearest neighbor queries. Although they are popular in low dimensional spaces, there are various reasons why Voronoi diagrams are rarely used higher dimensions. First, the combinatorial complexity of the diagram grows rapidly, as fast as Ω(nd/2) in d-dimensional space. Second, the diagram does not admit a straightforward search structure in higher dimensions. M3 - 10.1007/978-3-540-30551-4_2 ER -