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