The class cover problem with boxes

DOI10.1016/j.comgeo.2012.01.014zbMath1239.65015OpenAlexW2161667053MaRDI QIDQ419500

Sergio Cabello, José-Miguel Díaz-Báñez, Sergey Bereg, Carlos Seara, Inmaculada Ventura, Pablo Pérez-Lantero

Publication date: 18 May 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.01.014

zbMATH Keywords

classificationalgorithmscoveringNP-hardnessboxesgeometric optimization\(\varepsilon\)-netsclass cover

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions, The board packing problem, Classifying negative and positive points by optimal box clustering, On the geometric red-blue set cover problem, Computing the coarseness with strips or boxes, Classification using proximity catch digraphs

Cites Work

• Unnamed Item
• Improved approximation algorithms for geometric set cover
• Hitting sets when the VC-dimension is small
• \(\epsilon\)-nets and simplex range queries
• Geometric complexity of some location problems
• Approximation algorithms for the class cover problem
• Almost optimal set covers in finite VC-dimension
• A threshold of ln n for approximating set cover
• The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
• Covering Polygons Is Hard
• SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
• Tight lower bounds for the size of epsilon-nets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs