Simplex Range Searching and Its Variants: A Review
From MaRDI portal
Publication:4604367
Recommendations
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Lower Bounds on the Complexity of Polytope Range Searching
- Features of solving the range searching problems for d-dimensional case
- scientific article; zbMATH DE number 1241835
- Quasi-optimal range searching in spaces of finite VC-dimension
- -nets and simplex range queries
- On range searching with semialgebraic sets
- On range searching with semialgebraic sets
- Algorithms for generalized halfspace range searching and other intersection searching problems
- Algorithms for generalized halfspace range searching and other intersection searching problems
Cites work
- scientific article; zbMATH DE number 3911765 (Why is no real title available?)
- scientific article; zbMATH DE number 1241835 (Why is no real title available?)
- scientific article; zbMATH DE number 1182924 (Why is no real title available?)
- scientific article; zbMATH DE number 1528185 (Why is no real title available?)
- scientific article; zbMATH DE number 1424305 (Why is no real title available?)
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- A Lower Bound on the Complexity of Orthogonal Range Queries
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- A Randomized Algorithm for Closest-Point Queries
- A Spectral Approach to Lower Bounds with Applications to Geometric Searching
- A deterministic view of random sampling and its use in geometry
- A general approach for cache-oblivious range reporting and approximate range counting
- A linear algorithm for determining the separation of convex polyhedra
- A space-optimal solution of general region location
- Algorithms for ray-shooting and intersection searching
- Applications of a new space-partitioning technique
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Approximate halfspace range counting
- Approximate polytope membership queries
- Approximate range searching
- Approximate range searching in higher dimension
- Approximate range searching: The absolute model
- Computational geometry. Algorithms and applications.
- Construction of \(\epsilon\)-nets
- Cutting hyperplane arrangements
- Cutting hyperplanes for divide-and-conquer
- Efficient partition trees
- Filtering Search: A New Approach to Query-Answering
- General methods for adding range restrictions to decomposable searching problems
- Geometric applications of a randomized optimization technique
- Geometric retrieval problems
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Halfspace range search: An algorithmic application of k-sets
- How hard is half-space range searching?
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
- Improved range searching lower bounds
- Intersection Queries in Curved Objects
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Linear Optimization Queries
- Linear data structures for fast ray-shooting amidst convex polyhedra
- Linear programming queries revisited
- Lower Bounds on the Complexity of Some Optimal Data Structures
- Lower bounds for orthogonal range searching: part II. The arithmetic model
- Multidimensional binary search trees used for associative searching
- Multidimensional divide-and-conquer
- Multilevel polynomial partitions and simplified range searching
- New applications of random sampling in computational geometry
- New lower bounds for Hopcroft's problem
- Non-partitionable point sets
- On Approximating the Depth and Related Problems
- On range searching in the group model and combinatorial discrepancy
- On range searching with semialgebraic sets
- On range searching with semialgebraic sets. II.
- On ray shooting in convex polytopes
- On the Complexity of Maintaining Partial Sums
- On the Erdős distinct distances problem in the plane
- Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
- Optimal halfspace range reporting in three dimensions
- Optimal partition trees
- Partitioning Space for Range Queries
- Polygon Retrieval
- Polygonal intersection searching
- Quasi-optimal range searching in spaces of finite VC-dimension
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- Range minima queries with respect to a random permutation, and approximate range counting
- Range searching with efficient hierarchical cuttings
- Ray Shooting Amidst Convex Polygons in 2D
- Ray Shooting Amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions
- Ray Shooting and Parametric Search
- Refined bounds on the number of connected components of sign conditions on a variety
- Relative (p, )-approximations in geometry
- Reporting points in halfspaces
- Semialgebraic Range Reporting and Emptiness Searching with Applications
- Sharp bounds for vertical decompositions of linear arrangements in four dimensions
- Simplex range reporting on a pointer machine
- Space searching for intersecting objects
- Space-Time Tradeoffs for Emptiness Queries
- The power of geometric duality
- Tight lower bounds for halfspace range searching
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
- Visibility and intersection problems in plane geometry
- -nets and simplex range queries
Cited in
(19)- scientific article; zbMATH DE number 7559226 (Why is no real title available?)
- New variants of perfect non-crossing matchings
- Dynamic geometric data structures via shallow cuttings
- Throwing a sofa through the window
- On semialgebraic range reporting
- scientific article; zbMATH DE number 7204982 (Why is no real title available?)
- Polynomial data structure lower bounds in the group model
- The effect of corners on the complexity of approximate range searching
- Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
- On ray shooting for triangles in 3-space and related problems
- scientific article; zbMATH DE number 7559205 (Why is no real title available?)
- New variants of perfect non-crossing matchings
- General methods for adding range restrictions to decomposable searching problems
- Simplex range reporting on a pointer machine
- scientific article; zbMATH DE number 7559224 (Why is no real title available?)
- On reverse shortest paths in geometric proximity graphs
- Time and space efficient collinearity indexing
- Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
- On 3SUM-hard problems in the decision tree model
This page was built for publication: Simplex Range Searching and Its Variants: A Review
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604367)
