# On the Complexity of Randomly Weighted Multiplicative Voronoi Diagrams

Sariel Har-Peled, Benjamin Raichel

Research output: Contribution to journalArticlepeer-review

## Abstract

We provide an $$O(n \,\hbox {polylog}\, n)$$O(npolylogn) bound on the expected complexity of the randomly weighted multiplicative Voronoi diagram of a set of $$n$$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 on 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. (Discrete Comput Geom 54:551–582, 2014) 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.

Original language English (US) 547-568 22 Discrete and Computational Geometry 53 3 https://doi.org/10.1007/s00454-015-9675-0 Published - Apr 1 2015

## Keywords

• Arrangements
• Randomized incremental construction
• Voronoi diagrams

## ASJC Scopus subject areas

• Theoretical Computer Science
• Geometry and Topology
• Discrete Mathematics and Combinatorics
• Computational Theory and Mathematics

## Fingerprint

Dive into the research topics of 'On the Complexity of Randomly Weighted Multiplicative Voronoi Diagrams'. Together they form a unique fingerprint.