Quasi-optimal range searching in spaces of finite VC-dimension
From MaRDI portal
Publication:1823698
DOI10.1007/BF02187743zbMath0681.68081OpenAlexW2025809050WikidataQ54309753 ScholiaQ54309753MaRDI QIDQ1823698
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131092
Related Items
On range searching with semialgebraic sets, Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs, Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements, Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Rectilinear decompositions with low stabbing number, Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension, On intersection searching problems involving curved objects, Tight upper bounds for the discrepancy of half-spaces, FITTING A STEP FUNCTION TO A POINT SET WITH OUTLIERS BASED ON SIMPLICIAL THICKNESS DATA STRUCTURES, Cuttings for disks and axis-aligned rectangles in three-space, Almost optimal set covers in finite VC-dimension, The VC-dimension of set systems defined by graphs, Improved upper bounds for approximation by zonotopes, Simplex range reporting on a pointer machine, The VC dimension of metric balls under Fréchet and Hausdorff distances, Tight lower bounds for halfspace range searching, Optimal partition trees, Relative \((p,\varepsilon )\)-approximations in geometry, Simplex Range Searching and Its Variants: A Review, Storing line segments in partition trees, Sign rank versus Vapnik-Chervonenkis dimension, A Sauer-Shelah-Perles lemma for lattices, Construction of \(\epsilon\)-nets, Spanning trees crossing few barriers, Many disjoint edges in topological graphs, Partitioning arrangements of lines. II: Applications, On the Most Likely Voronoi Diagram and Nearest Neighbor Searching, Minimum-link paths revisited, Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures, Almost tight bounds for \(\epsilon\)-nets, On counting pairs of intersecting segments and off-line triangle range searching, On separating points by lines, Many disjoint edges in topological graphs, Reporting points in halfspaces, Applications of a new space-partitioning technique, Intersection queries in sets of disks, How hard is half-space range searching?, Range searching with efficient hierarchical cuttings, Efficient partition trees, On \(k\)-convex point sets, Tight bounds for connecting sites across barriers, Quasi-optimal upper bounds for simplex range searching and new zone theorems, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses, Lower Bounds on the Complexity of Polytope Range Searching, Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique, Intersection queries in sets of disks, Unnamed Item, Efficient image retrieval through vantage objects, Spanning trees with low crossing number, Two proofs for shallow packings, Lower bounds on the complexity of simplex range reporting on a pointer machine, Disjoint edges in complete topological graphs, VC-dimension and Erdős-Pósa property, Near-linear algorithms for geometric hitting sets and set covers, Minimizing the stabbing number of matchings, trees, and triangulations, Implicitly representing arrangements of lines or segments, On range searching with semialgebraic sets, Convex subdivisions with low stabbing numbers, Approximate range searching, Discrepancy and approximations for bounded VC-dimension, Fast Diameter Computation within Split Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast detection of polyhedral intersection
- Visibility and intersection problems in plane geometry
- \(\epsilon\)-nets and simplex range queries
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Central limit theorems for empirical measures
- Implicitly representing arrangements of lines or segments
- Density and dimension
- On the density of families of sets
- On the Complexity of Maintaining Partial Sums
- Combinatorial solutions of multidimensional divide-and-conquer recurrences
- Lower Bounds on the Complexity of Some Optimal Data Structures
- Polygon Retrieval
- Efficiency of a Good But Not Linear Set Union Algorithm
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
