$\epsilon$-nets and simplex range queries

DOI10.1007/BF02187876zbMath0619.68056OpenAlexW2054459484WikidataQ54309840 ScholiaQ54309840MaRDI QIDQ1089803

Publication date: 1987

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

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

zbMATH Keywords

counting problem data structure partition tree structure partitioning point sets query half space simplex range queries sublinear 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)

Related Items

Tighter estimates for $\epsilon$-nets for disks, Using $\varepsilon$-nets for linear separation of two sets in a Euclidean space $\mathbb R^d$, Testing geometric objects, On range searching with semialgebraic sets, Point location among hyperplanes and unidirectional ray-shooting, Efficient ray shooting and hidden surface removal, How to catch marathon cheaters: new approximation algorithms for tracking paths, Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements, On the dilation spectrum of paths, cycles, and trees, Almost tight upper bounds for lower envelopes in higher dimensions, The probabilistic method yields deterministic parallel algorithms, Sphere packing numbers for subsets of the Boolean $n$-cube with bounded Vapnik-Chervonenkis dimension, Unsplittable coverings in the plane, Cuttings for disks and axis-aligned rectangles in three-space, Inclusion-exclusion complexes for pseudodisk collections, From proximity to utility: a Voronoi partition of Pareto optima, Solving the classification problem using $\varepsilon$-nets, The VC-dimension of graphs with respect to $k$-connected subgraphs, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, The VC-dimension of set systems defined by graphs, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Improved results on geometric hitting set problems, Guarding galleries where every point sees a large area, Approximate testing and its relationship to learning, Small strong epsilon nets, VC-dimension of perimeter visibility domains, Clique versus independent set, A note about weak $\epsilon $-nets for axis-parallel boxes in $d$-space, Hardness of discrepancy computation and $\varepsilon$-net verification in high dimension, The class cover problem with boxes, Tight lower bounds for halfspace range searching, Optimal partition trees, Guarding scenes against invasive hypercubes., Range minima queries with respect to a random permutation, and approximate range counting, On the union of cylinders in three dimensions, On the approximability of covering points by lines and related problems, Relative $(p,\varepsilon )$-approximations in geometry, An optimal generalization of the colorful Carathéodory theorem, Piercing quasi-rectangles-on a problem of Danzer and Rogers, Storing line segments in partition trees, Partitioning arrangements of lines. I: An efficient deterministic algorithm, Construction of $\epsilon$-nets, Combinatorial complexity bounds for arrangements of curves and spheres, Polychromatic coloring for half-planes, Partitioning arrangements of lines. II: Applications, An optimal extension of the centerpoint theorem, Cutting hyperplane arrangements, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, On strong centerpoints, A non-linear lower bound for planar epsilon-nets, Minimizing interference of a wireless ad-hoc network in a plane, On disjoint concave chains in arrangements of (pseudo) lines, Equivalence of models for polynomial learnability, Almost tight bounds for $\epsilon$-nets, Optimal randomized parallel algorithms for computational geometry, $\varepsilon$-approximations of $k$-label spaces, On intersecting a point set with Euclidean balls, On counting pairs of intersecting segments and off-line triangle range searching, Constrained versions of Sauer's Lemma, An algorithm to construct separable $\epsilon$-nets of two sets, Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, On the Beer index of convexity and its variants, Reporting points in halfspaces, Intersection queries in sets of disks, How hard is half-space range searching?, Diameter, width, closest line pair, and parametric searching, On ray shooting in convex polytopes, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Efficient partition trees, Dynamic point location in arrangements of hyperplanes, Quasi-optimal upper bounds for simplex range searching and new zone theorems, $\varepsilon$-Mnets: Hitting geometric set systems with subsets, Lower bounds for weak epsilon-nets and stair-convexity, Bounding sample size with the Vapnik-Chervonenkis dimension, Cutting hyperplanes for divide-and-conquer, Compression schemes, stable definable families, and o-minimal structures, Reprint of: Weak $\varepsilon$-nets have basis of size $O(1/{\epsilon}\log (1/\epsilon))$ in any dimension, The complexity and construction of many faces in arrangements of lines and of segments, The complexity of many cells in arrangements of planes and related problems, $k$-Fold unions of low-dimensional concept classes, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, Two proofs for shallow packings, Random constructions and density results, A note on smaller fractional Helly numbers, Implicitly representing arrangements of lines or segments, Coloring geometric range spaces, A deterministic view of random sampling and its use in geometry, Prediction-preserving reducibility, Small weak epsilon-nets, Guarding galleries where no point sees a small area., New results on lower bounds for the number of $(\leq k)$-facets, Hitting sets when the VC-dimension is small, On the transversal number and VC-dimension of families of positive homothets of a convex body, Dynamic partition trees, Combinatorics and connectionism, Discrepancy and approximations for bounded VC-dimension, Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements, On sparse approximations to randomized strategies and convex combinations, Bounding the vertex cover number of a hypergraph, Unlabeled sample compression schemes and corner peelings for ample and maximum classes, Optimal approximations made easy, Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces, On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants, Geometric Hitting Sets for Disks: Theory and Practice, Tight upper bounds for the discrepancy of half-spaces, Exact learning from an honest teacher that answers membership queries, Triangles in space or building (and analyzing) castles in the air, An algorithm for generalized point location and its applications, A crossing lemma for Jordan curves, Around the Danzer problem and the construction of dense forests, Almost optimal set covers in finite VC-dimension, Vertical decompositions for triangles in 3-space, Small violations of Bell inequalities for multipartite pure random states, Lines in space: Combinatorics and algorithms, On the geometric set multicover problem, The $\varepsilon$-$t$-net problem, Computing depth orders for fat objects and related problems, Simplex range reporting on a pointer machine, Point location in zones of $k$-flats in arrangements, Independence number and the complexity of families of sets, Quasi-Monte-Carlo methods and the dispersion of point sequences, The VC dimension of metric balls under Fréchet and Hausdorff distances, Convex hulls under uncertainty, Randomized geometric algorithms and pseudorandom generators, ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE, On the VC-Dimension of Binary Codes, An efficient randomized algorithm for higher-order abstract Voronoi diagrams, A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, From a $(p, 2)$-theorem to a tight $(p, q)$-theorem, Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location, Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl, A Distributed Algorithm to Approximate Node-Weighted Minimum α-Connected (θ,k)-Coverage in Dense Sensor Networks, Near-linear approximation algorithms for geometric hitting sets, System of unbiased representatives for a collection of bicolorings, Simplex Range Searching and Its Variants: A Review, One-Sided Epsilon-Approximants, Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems, Teaching and Compressing for Low VC-Dimension, Ham-sandwich cuts for abstract order types, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS, Random sampling with removal, Practical and efficient algorithms for the geometric hitting set problem, Sign rank versus Vapnik-Chervonenkis dimension, A Sauer-Shelah-Perles lemma for lattices, Random polytopes and the wet part for arbitrary probability distributions, Trimming of graphs, with application to point labeling, On weak $\epsilon$-nets and the Radon number, On the VC-dimension of unique round-trip shortest path systems, Approximating a convex body by a polytope using the epsilon-net theorem, Core-Sets: Updated Survey, Sublinear search spaces for shortest path planning in grid and road networks, Robust Tverberg and Colourful Carathéodory Results via Random Choice, Building an optimal point-location structure in $O(\operatorname{sort}(n))$ I/Os, On separating points by lines, Domination in tournaments, On the number of points in general position in the plane, Domain adaptation -- can quantity compensate for quality?, Family Complexity and VC-Dimension, Weak $\varepsilon $-nets have basis of size $O(1/\varepsilon\log (1/\varepsilon))$ in any dimension, Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D, Tight lower bounds for the size of epsilon-nets, Approximate range searching using binary space partitions, Lower Bounds on the Complexity of Polytope Range Searching, Radon numbers and the fractional Helly theorem, RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS, Spanning trees with low crossing number, Active-learning a convex body in low dimensions, Planar point sets determine many pairwise crossing segments, Near-linear algorithms for geometric hitting sets and set covers, Packing and covering balls in graphs excluding a minor, Constructing arrangements optimally in parallel, Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks, When are epsilon-nets small?, A new lower bound on Hadwiger-Debrunner numbers in the plane, Large Area Convex Holes in Random Point Sets, On the VC-dimension and boolean functions with long runs, Efficient randomized algorithms for some geometric optimization problems, Testing proximity to subspaces: approximate $\ell_\infty$ minimization in constant time, New applications of random sampling in computational geometry, Bounded $VC$-dimension implies the Schur-Erdős conjecture, A general lower bound on the number of examples needed for learning, Applications of random sampling in computational geometry. II, A fast Las Vegas algorithm for triangulating a simple polygon, Quasi-optimal range searching in spaces of finite VC-dimension, A randomized algorithm for fixed-dimensional linear programming, Subsampling in Smoothed Range Spaces, The Vapnik-Chervonenkis dimension of a random graph, Small candidate set for translational pattern search, Bounding the trace function of a hypergraph with applications, Counting and representing intersections among triangles in three dimensions, Dot products in $\mathbb{F}_q^3$ and the Vapnik-Chervonenkis dimension, Efficient searching with linear constraints, Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model, On computing the diameter of a point set in high dimensional Euclidean space., Transversal numbers for hypergraphs arising in geometry, Multilevel polynomial partitions and simplified range searching, Fast segment insertion and incremental construction of constrained Delaunay triangulations, Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, Algorithms for polytope covering and approximation, A survey of mass partitions, Journey to the Center of the Point Set, A note on stabbing convex bodies with points, lines, and flats, Danzer's problem, effective constructions of dense forests and digital sequences, On the geometric priority set cover problem, Epsilon-nets for halfplanes, VC-dimensions for graphs (extended abstract), Unnamed Item, Deterministic Fault-Tolerant Connectivity Labeling Scheme, Unnamed Item, Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions., Pseudofinite groups and VC-dimension, On the number of regular vertices of the union of Jordan regions, On approximate range counting and depth, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, Dynamic partition trees, A lower bound for families of Natarajan dimension $d$, Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses, Intersection queries in sets of disks, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Incidences in Three Dimensions and Distinct Distances in the Plane, Computing coverage kernels under restricted settings, Lower bounds on the complexity of simplex range reporting on a pointer machine, Sparse Approximation via Generating Point Sets, Capacitated discrete unit disk cover, An efficient container lemma, Extending the centerpoint theorem to multiple points, On range searching with semialgebraic sets, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, On Partial Covering For Geometric Set Systems, Unnamed Item, Unnamed Item, Using $$\epsilon $$ -nets for Solving the Classification Problem

Cites Work

\(\epsilon\)-nets and simplex range queries