We investigate the combinatorial complexity of geodesic Voronoi
diagrams on polyhedral terrains using a probabilistic analysis.
Aronov etal [ABT08] prove that, if one makes certain
realistic input assumptions on the terrain, this complexity is
\Theta(n + m \sqrt n) in the worst case, where n
denotes the number of triangles that define the terrain and m
denotes the number of Voronoi sites. We prove that under a relaxed
set of assumptions the Voronoi diagram has expected complexity
O(n+m), given that the sites have a uniform distribution
on the domain of the terrain(or the surface of the terrain).
Furthermore, we present a worst-case construction of a terrain
which implies a lower bound of Vmega(n m^{2/3})
on the expected worst-case complexity if these assumptions on
the terrain are dropped. As an additional result, we can show
that the expected fatness of a cell in a random planar Voronoi
diagram is bounded by a constant.
PDF.
Last modified: Mon Nov 16 15:25:06 CST 2015