Startseite > Publikationen > Publikationen

Publikationen

Bienkowski, Marcin;Damerow, Valentina;Meyer auf der Heide, Friedhelm;Sohler, Christian:

Average Case Complexity of Voronoi Diagrams of n Sites from the Unit Cube.

In: Proceedings of the 21st European Workshop on Computational Geometry (EWCG'05), S. 167 - 170, , Jan. 2005

Abstract

We consider the expected number of Voronoi vertices (or number of Delaunay cells for the dual structure) for a set of n i.i.d. random point sites chosen uniformly from the unit d-hypercube. We show an upper bound for this number which is linear in n, the number of random point sites, where d is assumed to be a constant. This result matches the trivial lower bound of n. This is an open problem since several years. In 1991, Dwyer showed that for a uniform distribution from the unit d-ball the average number of Voronoi vertices is linear in n and it is commonly assumed that this holds for any reasonable probability distribution.

Dateien

hni2272.pdf



Bibtex

@inproceedings{hniid=2272,
author = {Bienkowski, Marcin and Damerow, Valentina and Meyer auf der Heide, Friedhelm and Sohler, Christian},
title = {Average Case Complexity of Voronoi Diagrams of n Sites from the Unit Cube},
booktitle = {Proceedings of the 21st European Workshop on Computational Geometry (EWCG'05)},
pages = {167 - 170, },
month = jan,
year = {2005},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/2272