The overlay of minimization diagrams in a randomized incremental construction
From MaRDI portal
Publication:633216
DOI10.1007/s00454-010-9324-6zbMath1211.52025MaRDI 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
arrangements; hyperplanes; Voronoi diagrams; overlays; randomized incremental construction; lower envelopes; minimization diagrams
52C35: Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
52C45: Combinatorial complexity of geometric structures
Related Items
On approximate range counting and depth, An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams, Unnamed Item, 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
