Higher-dimensional Voronoi diagrams in linear expected time

摘要

This work is the first to validate theoretically the suspicions of many researchers --- that the "average" Voronoi diagram is combinatorially quite simple and can be constructed quickly. Specifically, assuming that dimension d is fixed, and that n input points are chosen independently from the uniform distribution on the unit d-ball, it is proved that

the expected number of simplices of the dual of the Voronoi diagram is &THgr;(n) (exact constants are derived for the high-order term), and

a relatively simple algorithm exists for constructing the Voronoi diagram in &THgr;(n) time.

It is likely that the methods developed in the analysis will be applicable to other related quantities and other probability distributions.