TY - GEN

T1 - On the expected complexity of Voronoi diagrams on terrains

AU - Driemel, Anne

AU - Har-Peled, Sariel

AU - Raichel, Benjamin

PY - 2012/7/23

Y1 - 2012/7/23

N2 - We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et al. [AdBT08] prove that, if one makes certain realistic input assumptions on the terrain, this complexity is Θ(n+m√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 Ω(nm 2/3) on the expected worst-case complexity if these assumptions on the terrain are dropped.

AB - We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et al. [AdBT08] prove that, if one makes certain realistic input assumptions on the terrain, this complexity is Θ(n+m√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 Ω(nm 2/3) on the expected worst-case complexity if these assumptions on the terrain are dropped.

KW - Algorithms

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=84863919516&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863919516&partnerID=8YFLogxK

U2 - 10.1145/2261250.2261266

DO - 10.1145/2261250.2261266

M3 - Conference contribution

AN - SCOPUS:84863919516

SN - 9781450312998

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 101

EP - 110

BT - Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012

T2 - 28th Annual Symposuim on Computational Geometry, SCG 2012

Y2 - 17 June 2012 through 20 June 2012

ER -