The class cover problem with boxes

DOI10.1016/J.COMGEO.2012.01.014MaRDI QIDQ419500zbMATH OpenOpenAlexFDO

Authors S. Cabello, J. M. Díaz-Báñez, Sergey Bereg, P. Pérez-Lantero, Carlos Seara, I. Ventura

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

\(\varepsilon\)-netsalgorithmsboxesclass coverclassificationcoveringgeometric optimizationNP-hardness

Mathematics Subject Classification ID

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

Recommendations

• Covering points by disjoint boxes with outliers
• Covering point sets with two disjoint disks or squares
• Geometric red-blue set cover for unit squares and related problems
• Planar maximum-box problem revisited
• Square and Rectangle Covering with Outliers

Cites work

• -nets and simplex range queries
• A threshold of ln n for approximating set cover
• Almost optimal set covers in finite VC-dimension
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximation algorithms for the class cover problem
• Covering Polygons Is Hard
• Geometric complexity of some location problems
• Hitting sets when the VC-dimension is small
• scientific article; zbMATH DE number 1003231 (Why is no real title available?)
• Improved approximation algorithms for geometric set cover
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Small-size -nets for axis-parallel rectangles and boxes
• SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS
• The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
• Tight lower bounds for the size of epsilon-nets

Cited in

(19)

• Selecting and covering colored points
• The maximum exposure problem
• On the geometric red-blue set cover problem
• Classifying negative and positive points by optimal box clustering
• On covering Z-grid points by rectangles
• Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
• Choice is hard
• Computing the coarseness with strips or boxes
• Generalized class cover problem with axis-parallel strips
• Computing coverage kernels under restricted settings
• Computing coverage kernels under restricted settings
• The board packing problem
• Covering points by disjoint boxes with outliers
• Red-blue rectangular annulus cover problem
• Generalized class cover problem with axis-parallel strips
• Online class cover problem
• On the geometric red-blue set cover problem
• A low-rank tensor framework for hierarchical refinement in IgA
• Classification using proximity catch digraphs

This page was built for publication: The class cover problem with boxes

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