On the expected complexity of Voronoi diagrams on terrains

A. Driemel, S. Har-Peled, B. Raichel

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
1 Downloads (Pure)


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.

Original languageEnglish
Article number37
Pages (from-to)1-20
Number of pages20
JournalACM Transactions on Algorithms
Issue number3
Publication statusPublished - 1 Apr 2016


  • Random inputs
  • Voronoi diagrams on terrains


Dive into the research topics of 'On the expected complexity of Voronoi diagrams on terrains'. Together they form a unique fingerprint.

Cite this