On the Complexity of Randomly Weighted Voronoi Diagrams

DOI10.1145/2582112.2582158MaRDI QIDQ4635547zbMATH OpenOpenAlexFDO

Authors Benjamin Raichel, Sariel Har-Peled

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.1477

zbMATH Keywords

arrangementsVoronoi diagramsrandomized incremental construction

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Abstract: In this paper, we provide an $O(nmathrmpolylogn)$ 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 etal [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.

Recommendations

• On the complexity of randomly weighted multiplicative Voronoi diagrams
• The probabilistic complexity of the Voronoi diagram of points on a polyhedron
• On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
• On the expected complexity of Voronoi diagrams on terrains
• On the expected complexity of Voronoi diagrams on terrains
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• Higher-dimensional Voronoi diagrams in linear expected time
• On the complexity of higher order abstract Voronoi diagrams
• On the complexity of higher order abstract Voronoi diagrams

Cited in

(5)

• On the complexity of randomly weighted multiplicative Voronoi diagrams
• On the expected complexity of Voronoi diagrams on terrains
• From proximity to utility: a Voronoi partition of Pareto optima
• scientific article; zbMATH DE number 7651184 (Why is no real title available?)
• Linear expected complexity for directional and multiplicative Voronoi diagrams

This page was built for publication: On the Complexity of Randomly Weighted Voronoi Diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635547)