The overlay of minimization diagrams in a randomized incremental construction

DOI10.1007/s00454-010-9324-6zbMath1211.52025OpenAlexW1994009938MaRDI QIDQ633216

Micha Sharir, Haim Kaplan, Edgar A. Ramos

Publication date: 31 March 2011

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

Full work available at URL: https://doi.org/10.1007/s00454-010-9324-6

zbMATH Keywords

arrangementshyperplanesVoronoi diagramsoverlaysrandomized incremental constructionlower envelopesminimization diagrams

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Combinatorial complexity of geometric structures (52C45)

Related Items (7)

Range minima queries with respect to a random permutation, and approximate range counting ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ Unnamed Item ⋮ An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams ⋮ On approximate range counting and depth ⋮ A general approach for cache-oblivious range reporting and approximate range counting ⋮ On the complexity of randomly weighted multiplicative Voronoi diagrams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Range minima queries with respect to a random permutation, and approximate range counting
• Voronoi diagrams and arrangements
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Size-estimation framework with applications to transitive closure and reachability
• Cylindrical static and kinetic binary space partitions
• Applications of random sampling in computational geometry. II
• Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting
• On approximate halfspace range counting and relative epsilon-approximations
• On Approximating the Depth and Related Problems
• Lectures on Polytopes
• Constructing Planar Cuttings in Theory and Practice
• Approximate Halfspace Range Counting
• On approximate range counting and depth

This page was built for publication: The overlay of minimization diagrams in a randomized incremental construction