  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 m2/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.
