Quasi-optimal range searching in spaces of finite VC-dimension
From MaRDI portal
Publication:1823698
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 \(\delta \)-optimal space
Cites work
- 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?)
- 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
- 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 Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On the density of families of sets
- Polygon Retrieval
- Visibility and intersection problems in plane geometry
- \(\epsilon\)-nets and simplex range queries
Cited in
(75)- The VC dimension of metric balls under Fréchet and Hausdorff distances
- Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
- Efficient image retrieval through vantage objects
- Implicitly representing arrangements of lines or segments
- Efficient \(c\)-oriented range searching with DOP-trees
- Spanning trees with low crossing number
- On counting pairs of intersecting segments and off-line triangle range searching
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Improved upper bounds for approximation by zonotopes
- Storing line segments in partition trees
- Almost tight bounds for \(\epsilon\)-nets
- Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
- Relative \((p,\varepsilon )\)-approximations in geometry
- How hard is half-space range searching?
- Approximate range searching
- Range searching with efficient hierarchical cuttings
- Convex subdivisions with low stabbing numbers
- Efficient partition trees
- On range searching with semialgebraic sets
- Simplex range reporting on a pointer machine
- Rectilinear decompositions with low stabbing number
- Tight bounds for connecting sites across barriers
- Tight lower bounds for halfspace range searching
- Simplex Range Searching and Its Variants: A Review
- The effect of corners on the complexity of approximate range searching
- Minimizing the stabbing number of matchings, trees, and triangulations
- Near-linear algorithms for geometric hitting sets and set covers
- Optimal partition trees
- Intersection queries in sets of disks
- On range searching with semialgebraic sets
- Disjoint edges in complete topological graphs
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Partitioning arrangements of lines. II: Applications
- Two proofs for shallow packings
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- Partitioning Space for Range Queries
- Fitting a step function to a point set with outliers based on simplicial thickness data structures
- Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)
- Applications of a new space-partitioning technique
- Reporting points in halfspaces
- Lower Bounds on the Complexity of Polytope Range Searching
- Cuttings for disks and axis-aligned rectangles in three-space
- Tight upper bounds for the discrepancy of half-spaces
- Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses
- Almost optimal set covers in finite VC-dimension
- On intersection searching problems involving curved objects
- The VC-dimension of set systems defined by graphs
- Intersection queries in sets of disks
- Optimal partition trees
- Discrepancy and approximations for bounded VC-dimension
- On \(k\)-convex point sets
- On the Most Likely Voronoi Diagram and Nearest Neighbor Searching
- Construction of \(\epsilon\)-nets
- Minimum-link paths revisited
- Features of solving the range searching problems for d-dimensional case
- Spanning trees crossing few barriers
- A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
- VC-dimension and Erdős-Pósa property
- Algorithms – ESA 2005
- A Sauer-Shelah-Perles lemma for lattices
- On k-d Range Search with Patricia Tries
- Fast diameter computation within split graphs
- Discrepancy and sparsity
- On separating points by lines
- TWO-DIMENSIONAL RANGE SEARCH BASED ON THE VORONOI DIAGRAM
- Many disjoint edges in topological graphs
- Algorithms for subpath convex hull queries and ray-shooting among segments
- Improved points approximation algorithms based on simplicial thickness data structures
- scientific article; zbMATH DE number 7559228 (Why is no real title available?)
- Implicit representation of sparse hereditary families
- Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Sign rank versus Vapnik-Chervonenkis dimension
- Many disjoint edges in topological graphs
- scientific article; zbMATH DE number 1953130 (Why is no real title available?)
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)
