-nets and simplex range queries

DOI10.1007/BF02187876zbMATH Open0619.68056OpenAlexW2054459484WikidataQ54309840 ScholiaQ54309840MaRDI QIDQ1089803FDOQ1089803

Authors: David Haussler, Emo Welzl 

Publication date: 1987

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131015

Recommendations

• Construction of \(\epsilon\)-nets
• Almost tight bounds for \(\epsilon\)-nets
• Small-size ε-nets for axis-parallel rectangles and boxes
• Tight lower bounds for the size of epsilon-nets
• scientific article; zbMATH DE number 431986

zbMATH Keywords

data structurecounting problempartition tree structurepartitioning point setsquery half spacesimplex range queriessublinear time

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorial probability (60C05) Random convex sets and integral geometry (aspects of convex geometry) (52A22) Designs and configurations (05B99)

Cites Work

• Some special Vapnik-Chervonenkis classes
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Central limit theorems for empirical measures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Density and dimension
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Polygon Retrieval
• Constructing Belts in Two-Dimensional Arrangements with Applications
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• Capacitated discrete unit disk cover
• The probabilistic method yields deterministic parallel algorithms
• How to catch marathon cheaters: new approximation algorithms for tracking paths
• On the dilation spectrum of paths, cycles, and trees
• Cutting hyperplane arrangements
• Equivalence of models for polynomial learnability
• Storing line segments in partition trees
• Randomized geometric algorithms and pseudorandom generators
• A fast Las Vegas algorithm for triangulating a simple polygon
• On range searching with semialgebraic sets
• A randomized algorithm for fixed-dimensional linear programming
• Cuttings for disks and axis-aligned rectangles in three-space
• Efficient ray shooting and hidden surface removal
• Point location among hyperplanes and unidirectional ray-shooting
• The VC dimension of metric balls under Fréchet and Hausdorff distances
• Inclusion-exclusion complexes for pseudodisk collections
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Vertical decompositions for triangles in 3-space
• Computing depth orders for fat objects and related problems
• A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
• Guarding scenes against invasive hypercubes.
• Tight upper bounds for the discrepancy of half-spaces
• Robust Tverberg and Colourful Carathéodory Results via Random Choice
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses
• Convex hulls under uncertainty
• Exact learning from an honest teacher that answers membership queries
• Optimal, output-sensitive algorithms for constructing planar hulls in parallel
• A note on smaller fractional Helly numbers
• Bounding sample size with the Vapnik-Chervonenkis dimension
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Extending the centerpoint theorem to multiple points
• Range minima queries with respect to a random permutation, and approximate range counting
• SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
• Practical and efficient algorithms for the geometric hitting set problem
• Title not available (Why is that?)
• A survey of mass partitions
• On approximate range counting and depth
• An optimal generalization of the colorful Carathéodory theorem
• Construction of \(\epsilon\)-nets
• Triangles in space or building (and analyzing) castles in the air
• Family Complexity and VC-Dimension
• Intersection queries in sets of disks
• Simplex Range Searching and Its Variants: A Review
• Near-linear algorithms for geometric hitting sets and set covers
• Tight lower bounds for the size of epsilon-nets
• An algorithm to construct separable \(\epsilon\)-nets of two sets
• On the Beer index of convexity and its variants
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
• Dynamic partition trees
• Domination in tournaments
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Partitioning arrangements of lines. II: Applications
• Lower bounds on the complexity of simplex range reporting on a pointer machine
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• \(\varepsilon\)-approximations of \(k\)-label spaces
• On intersecting a point set with Euclidean balls
• Diameter, width, closest line pair, and parametric searching
• \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets
• Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
• Prediction-preserving reducibility
• \(k\)-Fold unions of low-dimensional concept classes
• Discrepancy and approximations for bounded VC-dimension
• An algorithm for generalized point location and its applications
• Title not available (Why is that?)
• Tighter estimates for \(\epsilon\)-nets for disks
• Lower bounds for weak epsilon-nets and stair-convexity
• Small strong epsilon nets
• Clique versus independent set
• Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
• Polychromatic coloring for half-planes
• A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space
• On ray shooting in convex polytopes
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Using \(\varepsilon\)-nets for linear separation of two sets in a Euclidean space \(\mathbb R^d\)
• Efficient searching with linear constraints
• Improved results on geometric hitting set problems
• An optimal extension of the centerpoint theorem
• Tight lower bounds for halfspace range searching
• A deterministic view of random sampling and its use in geometry
• Small weak epsilon-nets
• Title not available (Why is that?)
• Guarding galleries where no point sees a small area.
• On sparse approximations to randomized strategies and convex combinations
• The complexity of many cells in arrangements of planes and related problems
• Guarding galleries where every point sees a large area
• Random constructions and density results
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• On counting pairs of intersecting segments and off-line triangle range searching
• Hitting sets when the VC-dimension is small
• How hard is half-space range searching?
• Efficient randomized algorithms for some geometric optimization problems
• Almost tight bounds for \(\epsilon\)-nets
• Efficient partition trees
• Combinatorial complexity bounds for arrangements of curves and spheres
• Two proofs for shallow packings
• One-Sided Epsilon-Approximants
• Reporting points in halfspaces
• Cutting hyperplanes for divide-and-conquer

This page was built for publication: \(\epsilon\)-nets and simplex range queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1089803)