Almost optimal set covers in finite VC-dimension
From MaRDI portal
Publication:1906049
DOI10.1007/BF02570718zbMath0841.68122WikidataQ55883000 ScholiaQ55883000MaRDI QIDQ1906049
Hervé Brönnimann, Michael T. Goodrich
Publication date: 6 February 1996
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131414
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
Related Items
Decision Trees for Geometric Models, COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS, Covering Points by Unit Disks of Fixed Location, Domination in Geometric Intersection Graphs, Helly-type theorems for approximate covering, Combinatorial optimization algorithms for radio network planning, Bregman Voronoi diagrams, Improved results on geometric hitting set problems, Polynomial time approximation schemes for minimum disk cover problems, Guarding galleries and terrains, Approximately dominating representatives, Covering a line segment with variable radius discs, Hausdorff approximation of 3D convex polytopes, Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets, Hitting sets when the VC-dimension is small, On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees, Fast stabbing of boxes in high dimensions, Linear time approximation of 3D convex polytopes, Polynomial-time approximation schemes for piercing and covering with applications in wireless networks, On guarding the vertices of rectilinear domains, A Scheme for Computing Minimum Covers within Simple Regions, A Distributed Algorithm to Approximate Node-Weighted Minimum α-Connected (θ,k)-Coverage in Dense Sensor Networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Range searching with efficient hierarchical cuttings
- A deterministic view of random sampling and its use in geometry
- Construction of \(\epsilon\)-nets
- On learning a union of half spaces
- \(\epsilon\)-nets and simplex range queries
- Cutting hyperplane arrangements
- Almost tight bounds for \(\epsilon\)-nets
- Reporting points in halfspaces
- Efficient partition trees
- Cutting hyperplanes for divide-and-conquer
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- An optimal convex hull algorithm in any fixed dimension
- Discrepancy and approximations for bounded VC-dimension
- Applications of random sampling in computational geometry. II
- Quasi-optimal range searching in spaces of finite VC-dimension
- Density and dimension
- On the density of families of sets
- Learnability and the Vapnik-Chervonenkis dimension
- Approximation schemes for covering and packing problems in image processing and VLSI
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Product Range Spaces, Sensitive Sampling, and Derandomization
- Decision Trees for Geometric Models
- Reducibility among Combinatorial Problems
- Algorithms for polytope covering and approximation
- On the hardness of approximating minimization problems
- Efficient probabilistically checkable proofs and applications to approximations
- Improved bounds on weak ε-nets for convex sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
