\(\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 (only showing first 100 items - show all)

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

Cites Work

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