@inproceedings{58f6242b46234fe295f83e77b1566a91,
title = "On the complexity of randomly weighted Voronoi diagrams",
abstract = "In this paper, we provide an O(n polylog n) bound on the expected complexity of the randomly weighted Voronoi diagram of a set of n sites in the plane, where the sites can be either points, interior-disjoint convex sets, or other more general objects. Here the randomness is on the weight of the sites, not their location. This compares favorably with the worst case complexity of these diagrams, which is quadratic. As a consequence we get an alternative proof to that of Agarwal et al. [AHKS13] of the near linear complexity of the union of randomly expanded disjoint segments or convex sets (with an improved bound on the latter). The technique we develop is elegant and should be applicable to other problems.",
keywords = "Arrangements, Randomized incremental construction, Voronoi diagrams",
author = "Sariel Har-Peled and Benjamin Raichel",
year = "2014",
doi = "10.1145/2582112.2582158",
language = "English (US)",
isbn = "9781450325943",
series = "Proceedings of the Annual Symposium on Computational Geometry",
publisher = "Association for Computing Machinery",
pages = "232--241",
booktitle = "Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014",
address = "United States",
note = "30th Annual Symposium on Computational Geometry, SoCG 2014 ; Conference date: 08-06-2014 Through 11-06-2014",
}