On the Expected Complexity of Voronoi Diagrams on Terrains

Details On the Expected Complexity of Voronoi Diagrams on Terrains On the Expected Complexity of Voronoi Diagrams on Terrains

2011-12-03

arxiv.org/abs/1112.0695v1

Computer Science

Computational Geometry

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Expected Complexity of Voronoi Diagrams on Terrains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Expected Complexity of Voronoi Diagrams on Terrains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Expected Complexity of Voronoi Diagrams on Terrains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-387503