On the Complexity of Randomly Weighted Voronoi Diagrams

DOI10.1145/2582112.2582158zbMATH Open1401.68350arXiv1401.1477OpenAlexW2136499845MaRDI QIDQ4635547FDOQ4635547

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)

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.

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

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

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)

Cited In (5)

• Title not available (Why is that?)
• From proximity to utility: a Voronoi partition of Pareto optima
• Linear expected complexity for directional and multiplicative Voronoi diagrams
• On the expected complexity of Voronoi diagrams on terrains
• On the complexity of randomly weighted 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)