TY - JOUR

T1 - On the expected complexity of Voronoi diagrams on terrains

AU - Driemel, Anne

AU - Har-Peled, Sariel

AU - Raichel, Benjamin

N1 - Publisher Copyright:
© 2016 ACM.

PY - 2016/4

Y1 - 2016/4

N2 - We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et al. [2008] 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 mdenotes 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 are sampled uniformly at random from the domain of the terrain (or the surface of the terrain). Furthermore, we present a construction of a terrain that implies a lower bound of ω (nm2/3) on the expected worst-case complexity if these assumptions on the terrain are dropped. As an additional result, we show that the expected fatness of a cell in a random planar Voronoi diagram is bounded by a constant.

AB - We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et al. [2008] 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 mdenotes 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 are sampled uniformly at random from the domain of the terrain (or the surface of the terrain). Furthermore, we present a construction of a terrain that implies a lower bound of ω (nm2/3) on the expected worst-case complexity if these assumptions on the terrain are dropped. As an additional result, we show that the expected fatness of a cell in a random planar Voronoi diagram is bounded by a constant.

KW - Random inputs

KW - Voronoi diagrams on terrains

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

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

U2 - 10.1145/2846099

DO - 10.1145/2846099

M3 - Article

AN - SCOPUS:84968820734

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 3

M1 - 37

ER -