Quasi-optimal range searching in spaces of finite VC-dimension
From MaRDI portal
Publication:1823698
The paper deals with the range searching problem, i.e. given a finite set S of points in d-dimensional space \(E^ d\) and a query region \(q\subseteq E^ d\), report or count the points of \(S\cap q\). On more abstract level one can consider a range space (X,R), where X is an arbitrary set (the elements of X are called points) and R is a subset of its power set (the members of R are called ranges). The authors consider the use of partition trees to solve this problem and show that ``good partition trees (i.e. with sublinear query time and linear size) can be characterized as those defined by range spaces of finite Vapnik- Chervonenkis dimension. Then they show that simplex and spherical range searching problems are both solvable in \(\theta (n^{1-1/d}\alpha (n))\) query time and \(\theta\) (n) storage in the arithmetical model, where \(\alpha\) (n) denotes the inverse Ackerman function. Finally algorithms for polygon, disk and tetrahedron range searching on RAM or pointer machine are discussed.
Recommendations
- Tight lower bounds for halfspace range searching
- Tight lower bounds for halfspace range searching
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Orthogonal range searching in linear and almost-linear space
- Orthogonal Range Searching in Linear and Almost-Linear Space
- Approximate range searching in higher dimension
- Lower Bounds on the Complexity of Polytope Range Searching
- Approximate range searching using binary space partitions
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Near-optimal search time in -optimal space
Cites work
- -nets and simplex range queries
- Central limit theorems for empirical measures
- Combinatorial solutions of multidimensional divide-and-conquer recurrences
- Density and dimension
- Efficiency of a Good But Not Linear Set Union Algorithm
- Fast detection of polyhedral intersection
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- scientific article; zbMATH DE number 3887061 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- Implicitly representing arrangements of lines or segments
- Lower Bounds on the Complexity of Some Optimal Data Structures
- On the Complexity of Maintaining Partial Sums
- On the density of families of sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Polygon Retrieval
- Visibility and intersection problems in plane geometry
Cited in
(87)- Efficient \(c\)-oriented range searching with DOP-trees
- Minimizing the stabbing number of matchings, trees, and triangulations
- The effect of corners on the complexity of approximate range searching
- Convex subdivisions with low stabbing numbers
- Almost tight bounds for -nets
- Reporting points in halfspaces
- Applications of a new space-partitioning technique
- Intersection queries in sets of disks
- Efficient partition trees
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Implicitly representing arrangements of lines or segments
- Discrepancy and approximations for bounded VC-dimension
- On range searching with semialgebraic sets
- Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
- Rectilinear decompositions with low stabbing number
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- The VC-dimension of set systems defined by graphs
- Improved upper bounds for approximation by zonotopes
- Spanning trees crossing few barriers
- Approximate range searching
- Tight upper bounds for the discrepancy of half-spaces
- Almost optimal set covers in finite VC-dimension
- Simplex range reporting on a pointer machine
- On separating points by lines
- A Sauer-Shelah-Perles lemma for lattices
- On \(k\)-convex point sets
- Near-linear algorithms for geometric hitting sets and set covers
- Minimum-link paths revisited
- VC-dimension and Erdős-Pósa property
- The VC dimension of metric balls under Fréchet and Hausdorff distances
- Features of solving the range searching problems for d-dimensional case
- On the Most Likely Voronoi Diagram and Nearest Neighbor Searching
- Improved points approximation algorithms based on simplicial thickness data structures
- Spanning trees with low crossing number
- Lower Bounds on the Complexity of Polytope Range Searching
- On k-d Range Search with Patricia Tries
- Partitioning Space for Range Queries
- Tight lower bounds for halfspace range searching
- Optimal partition trees
- scientific article; zbMATH DE number 1953130 (Why is no real title available?)
- Simplex Range Searching and Its Variants: A Review
- Sign rank versus Vapnik-Chervonenkis dimension
- Fast diameter computation within split graphs
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- On intersection searching problems involving curved objects
- Intersection queries in sets of disks
- The VC dimension of metric balls under Fréchet and Hausdorff distances
- On range searching with semialgebraic sets
- Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
- Fitting a step function to a point set with outliers based on simplicial thickness data structures
- TWO-DIMENSIONAL RANGE SEARCH BASED ON THE VORONOI DIAGRAM
- Optimal partition trees
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Algorithms – ESA 2005
- A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
- Many disjoint edges in topological graphs
- Disjoint edges in complete topological graphs
- Many disjoint edges in topological graphs
- Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses
- Efficient image retrieval through vantage objects
- Relative (p, )-approximations in geometry
- Algorithms for subpath convex hull queries and ray-shooting among segments
- Discrepancy and sparsity
- Implicit representation of sparse hereditary families
- On counting pairs of intersecting segments and off-line triangle range searching
- How hard is half-space range searching?
- Range searching with efficient hierarchical cuttings
- An optimal sparsification lemma for low-crossing matchings and its applications to discrepancy and approximations
- On separating path and tree systems in graphs
- On short edges in complete topological graphs
- Computing diameter+2 in truly-subquadratic time for unit-disk graphs
- Semialgebraic range stabbing, ray shooting, and intersection counting in the plane
- Lower bounds for semialgebraic range searching and stabbing problems
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- Lower bounds for semialgebraic range searching and stabbing problems
- Escaping the curse of spatial partitioning: matchings with low crossing numbers and their applications
- Quantum algorithms for Hopcroft's problem
- Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
- Robust bichromatic classification using two lines
- Two proofs for shallow packings
- Sparse bounded hop-spanners for geometric intersection graphs
- Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
- Cuttings for disks and axis-aligned rectangles in three-space
- Storing line segments in partition trees
- Construction of \(\epsilon\)-nets
- Partitioning arrangements of lines. II: Applications
- Tight bounds for connecting sites across barriers
This page was built for publication: Quasi-optimal range searching in spaces of finite VC-dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823698)
