Higher-dimensional Voronoi diagrams in linear expected time
Rex A. Dwyer · 1989
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