TY - GEN

T1 - On the complexity of randomly weighted Voronoi diagrams

AU - Har-Peled, Sariel

AU - Raichel, Benjamin

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Arrangements

KW - Randomized incremental construction

KW - Voronoi diagrams

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

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

U2 - 10.1145/2582112.2582158

DO - 10.1145/2582112.2582158

M3 - Conference contribution

AN - SCOPUS:84904409220

SN - 9781450325943

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 232

EP - 241

BT - Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014

PB - Association for Computing Machinery

T2 - 30th Annual Symposium on Computational Geometry, SoCG 2014

Y2 - 8 June 2014 through 11 June 2014

ER -