On the expected complexity of Voronoi diagrams on terrains

Anne Driemel, Sariel Har-Peled, Benjamin Raichel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012
Pages101-110
Number of pages10
DOIs
StatePublished - Jul 23 2012
Event28th Annual Symposuim on Computational Geometry, SCG 2012 - Chapel Hill, NC, United States
Duration: Jun 17 2012Jun 20 2012

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other28th Annual Symposuim on Computational Geometry, SCG 2012
CountryUnited States
CityChapel Hill, NC
Period6/17/126/20/12

Keywords

  • Algorithms
  • Theory

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

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

Cite this