The overlay of minimization diagrams in a randomized incremental construction

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

Haim Kaplan, Micha Sharir, 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

arrangements; hyperplanes; Voronoi diagrams; overlays; randomized incremental construction; lower envelopes; minimization diagrams

Mathematics Subject Classification ID

52C35: Arrangements of points, flats, hyperplanes (aspects of discrete geometry)

52C45: Combinatorial complexity of geometric structures

Related Items

On approximate range counting and depth, Range minima queries with respect to a random permutation, and approximate range counting, Relative \((p,\varepsilon )\)-approximations in geometry, 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