Range minima queries with respect to a random permutation, and approximate range counting

DOI10.1007/s00454-010-9308-6zbMath1246.68105OpenAlexW2004222099MaRDI QIDQ629829

Micha Sharir, Haim Kaplan, Edgar A. Ramos

Publication date: 10 March 2011

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

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

zbMATH Keywords

random samplingrange searchingrange minima queriesapproximate range countingrandomized incremental constructions

Mathematics Subject Classification ID

Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (5)

Relative \((p,\varepsilon )\)-approximations in geometry ⋮ The overlay of minimization diagrams in a randomized incremental construction ⋮ Simplex Range Searching and Its Variants: A Review ⋮ On approximate range counting and depth ⋮ A general approach for cache-oblivious range reporting and approximate range counting

Uses Software

• Hull

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relative \((p,\varepsilon )\)-approximations in geometry
• The overlay of minimization diagrams in a randomized incremental construction
• Range searching with efficient hierarchical cuttings
• On ray shooting in convex polytopes
• Four results on randomized incremental constructions
• Point location in arrangements of hyperplanes
• Voronoi diagrams and arrangements
• \(\epsilon\)-nets and simplex range queries
• Randomized incremental construction of Delaunay and Voronoi diagrams
• Reporting points in halfspaces
• Efficient partition trees
• Size-estimation framework with applications to transitive closure and reachability
• Applications of random sampling in computational geometry. II
• Ray Shooting and Parametric Search
• 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
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• Approximate Halfspace Range Counting
• The maximum numbers of faces of a convex polytope
• On approximate range counting and depth
• Improved bounds on the sample complexity of learning

This page was built for publication: Range minima queries with respect to a random permutation, and approximate range counting