Simplex Range Searching and Its Variants: A Review
From MaRDI portal
Publication:4604367
DOI10.1007/978-3-319-44479-6_1zbMath1423.68530OpenAlexW2762290866MaRDI QIDQ4604367
Publication date: 26 February 2018
Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-44479-6_1
Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (16)
New variants of perfect non-crossing matchings ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ On Ray Shooting for Triangles in 3-Space and Related Problems ⋮ Time and space efficient collinearity indexing ⋮ On reverse shortest paths in geometric proximity graphs ⋮ Throwing a sofa through the window ⋮ On semialgebraic range reporting ⋮ Dynamic geometric data structures via shallow cuttings ⋮ New variants of perfect non-crossing matchings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications ⋮ Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model ⋮ On 3SUM-hard problems in the decision tree model
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multidimensional divide-and-conquer
- Refined bounds on the number of connected components of sign conditions on a variety
- Tight lower bounds for halfspace range searching
- Optimal partition trees
- On the Erdős distinct distances problem in the plane
- Range minima queries with respect to a random permutation, and approximate range counting
- Relative \((p,\varepsilon )\)-approximations in geometry
- How hard is half-space range searching?
- Range searching with efficient hierarchical cuttings
- On ray shooting in convex polytopes
- Sharp bounds for vertical decompositions of linear arrangements in four dimensions
- A deterministic view of random sampling and its use in geometry
- Linear data structures for fast ray-shooting amidst convex polyhedra
- Visibility and intersection problems in plane geometry
- Construction of \(\epsilon\)-nets
- A general approach for cache-oblivious range reporting and approximate range counting
- Non-partitionable point sets
- Halfspace range search: An algorithmic application of k-sets
- The power of geometric duality
- \(\epsilon\)-nets and simplex range queries
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- General methods for adding range restrictions to decomposable searching problems
- A space-optimal solution of general region location
- Polygonal intersection searching
- Cutting hyperplane arrangements
- Reporting points in halfspaces
- Applications of a new space-partitioning technique
- Efficient partition trees
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Cutting hyperplanes for divide-and-conquer
- On range searching with semialgebraic sets
- Approximate range searching
- Geometric applications of a randomized optimization technique
- New lower bounds for Hopcroft's problem
- New applications of random sampling in computational geometry
- Quasi-optimal range searching in spaces of finite VC-dimension
- Simplex range reporting on a pointer machine
- Approximate range searching: The absolute model
- Multilevel polynomial partitions and simplified range searching
- Approximate range searching in higher dimension
- Improved range searching lower bounds
- IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS
- Semialgebraic Range Reporting and Emptiness Searching with Applications
- Ray Shooting and Parametric Search
- Intersection Queries in Curved Objects
- Lower bounds for orthogonal range searching: part II. The arithmetic model
- On Approximating the Depth and Related Problems
- On the Complexity of Maintaining Partial Sums
- A linear algorithm for determining the separation of convex polyhedra
- Geometric retrieval problems
- Filtering Search: A New Approach to Query-Answering
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- A Randomized Algorithm for Closest-Point Queries
- Partitioning Space for Range Queries
- Ray Shooting Amidst Convex Polygons in 2D
- Lower Bounds on the Complexity of Some Optimal Data Structures
- A Lower Bound on the Complexity of Orthogonal Range Queries
- Polygon Retrieval
- Algorithms for ray-shooting and intersection searching
- Multidimensional binary search trees used for associative searching
- Las Vegas algorithms for linear and integer programming when the dimension is small
- A Spectral Approach to Lower Bounds with Applications to Geometric Searching
- Space-Time Tradeoffs for Emptiness Queries
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- Linear Optimization Queries
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- Ray Shooting Amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions
- Linear programming queries revisited
- Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
- Approximate Halfspace Range Counting
- On Range Searching with Semialgebraic Sets. II
- Approximate polytope membership queries
- On Range Searching in the Group Model and Combinatorial Discrepancy
- Space searching for intersecting objects
- 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
This page was built for publication: Simplex Range Searching and Its Variants: A Review
