Higher-dimensional voronoi diagrams in linear expected time

By Rex A. Dwyer. 1989

A general method is presented for determining the mathematical expectation of the combinatorial complexity and other properties of the Voronoi diagram ofn independent and identically distributed points. The method is applied to derive exact asymptotic bounds on the expected number of vertices of the Voronoi diagram of points chosen from the uniform distribution on the interior of ad-dimensional ball; it is shown that in this case, the complexity of the diagram is ∵(n) for fixedd. An algorithm for constructing the Voronoid diagram is presented and analyzed. The algorithm is shown to require only ∵(n) time on average for random points from ad-ball assuming a real-RAM model of computation with a constant-time floor function. This algorithm is asymptotically faster than any previously known and optimal in the average-case sense.

Subfields: Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, background): “…average degree of a node in the Delaunay graph is capped by a constant C in the limit of the large dataset (this is the case for random Euclid data [48], but can be in principle violated in exotic spaces), then the overall average number of distance evaluations in a layer is bounded by a constant…”
MOLE 2.0: advanced approach for analysis of biomacromolecular channels (2013, methodology): “However, as shown by Dwyer et al. [47], in most cases M = O ( N ).”
Intentional motion on-line learning and prediction (2008, background): “This means that the number of links in it is O(N ) [14], also, as demonstrated by [16], in most cases, this property still holds for higher dimensional spaces.”
State of the Union (of geometric objects) (2008, unknown): “Dwyer [42] has proved that the expected size of the (Euclidean) Voronoi diagram of a set of uniformly distributed random points inside a ball in R is linear.”