Average case complexity of Voronoi diagrams of n sites from the unit cube
Marcin Bieńkowski, Valentina Damerow, Friedhelm Meyer auf der Heide, Christian Sohler · 2005
We consider the expected number of Voronoi vertices (or number of Delaunay cells for the dual structure) for a set of n i.i.d. random point sites chosen uniformly from the unit d-hypercube [0, 1] d . We show an upper bound for this number which is linear in n, the number of random point sites, where d is assumed to be a constant. This result matches the trivial lower bound of n. This is an open problem since several years. In 1991, Dwyer [2] showed that for a uniform distribution from the unit d-ball the average number of Voronoi vertices is linear in n and it is commonly assumed that this holds for any reasonable probability distribution.