Geometric red-blue set cover for unit squares and related problems

DOI10.1016/j.comgeo.2014.12.005zbMath1314.65029OpenAlexW2144614313MaRDI QIDQ2341691

Timothy M. Chan, Nan Hu

Publication date: 27 April 2015

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

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

zbMATH Keywords

dynamic programmingapproximation algorithmsgeometric set coverred-blue set cover problem

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (19)

\(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point ⋮ Approximability and hardness of geometric hitting set with axis-parallel rectangles ⋮ Weighted geometric set cover with rectangles of bounded integer side lengths ⋮ Dynamic Minimum Bichromatic Separating Circle ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares ⋮ On the geometric red-blue set cover problem ⋮ Discrete unit square cover problem ⋮ Algorithms and complexity for a class of combinatorial optimization problems with labelling ⋮ Minimum membership covering and hitting ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Maximum independent and disjoint coverage ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Approximability of covering cells with line segments ⋮ Covering uncertain points in a tree ⋮ On Partial Covering For Geometric Set Systems ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting

Cites Work

• Improved results on geometric hitting set problems
• Unit disk graphs
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• PTAS for Weighted Set Cover on Unit Squares
• Approximation schemes for covering and packing problems in image processing and VLSI
• Polynomial-time approximation schemes for packing and piercing fat objects
• Approximation algorithms for partial covering problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Geometric red-blue set cover for unit squares and related problems