On the complexity of randomly weighted multiplicative Voronoi diagrams

DOI10.1007/s00454-015-9675-0zbMath1318.52019OpenAlexW2009862760MaRDI QIDQ2349856

Sariel Har-Peled, Benjamin Raichel

Publication date: 18 June 2015

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-015-9675-0

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)

Related Items (9)

The impact of heterogeneity and geometry on the proof complexity of random satisfiability ⋮ Unnamed Item ⋮ Union of random Minkowski sums and network vulnerability analysis ⋮ Union of Hypercubes and 3D Minkowski Sums with Random Sizes. ⋮ An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams ⋮ Union of hypercubes and 3D Minkowski sums with random sizes ⋮ On the recognition and reconstruction of weighted Voronoi diagrams and bisector graphs ⋮ Abstract Voronoi Diagrams from Closed Bisecting Curves ⋮ On the complexity of randomly weighted multiplicative Voronoi diagrams

Cites Work

• Union of random Minkowski sums and network vulnerability analysis
• The overlay of minimization diagrams in a randomized incremental construction
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• Abstract Voronoi diagrams revisited
• Almost tight upper bounds for lower envelopes in higher dimensions
• An output sensitive algorithm for discrete convex hulls
• Applications of random sampling in computational geometry. II
• On the complexity of randomly weighted multiplicative Voronoi diagrams
• Voronoi Diagrams and Delaunay Triangulations
• On the expected complexity of voronoi diagrams on terrains
• Power Diagrams: Properties, Algorithms and Applications
• Union of random minkowski sums and network vulnerability analysis
• Sharp bounds on Davenport-Schinzel sequences of every order
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• [https://portal.mardi4nfdi.de/wiki/Publication:5728818 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten]
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of randomly weighted multiplicative Voronoi diagrams