Approximability and hardness of geometric hitting set with axis-parallel rectangles
Introduction
Let be a set of points and be a set of objects in the plane. We say that a subset is a hitting set for if every object in contains at least one point in . In the hitting set problem, we are given and the goal is to find a minimum size hitting set of points for objects in . In weighted version of the problem, every point is given a non-negative weight and the goal is to find a hitting set for with minimum . In this paper, we consider the following two hitting set problems.
Problem 1 Rect-Hit. All the objects in are axis-parallel rectangles.
Problem 2 Rect-Hit-Bounded. This is a special case of Rect-Hit problem where the side lengths of rectangles are integers less than or equal to C, where C is a constant.
We now discuss some previous work and our discussion is confined to only axis-parallel rectangles.
General axis-parallel rectangles. Recently, in one of our papers [10], we show that the hitting set problem is -hard when contains only two types of integer dimension axis-parallel rectangles and the rectangles share a common point. On the other hand, the hitting set problem is known to be -hard [3] even for two types of rectangles. The best-known approximation factor for hitting set with axis-parallel rectangles is [2].
Bounded side length axis-parallel rectangles. The hitting set problem is known to be -hard for unit squares [6]. However, three es are known for the hitting set problem with unit squares, one in unweighted case [12] and two by duality from es for weighted set cover [5], [4].
For objects in Problem 2, a is known for set cover problem [11]. However, as our objects are not unit squares, this does not give a for Problem 2 by duality.
The major contributions of the paper are as follows:
- 1.
We define a special hitting set problem - and show that it is hard (see Section 2).
- 2.
We prove that Problem 1 is -hard even when origin in the plane is inside all rectangles by giving a reduction from - (see Section 3). We use - to prove -hardness of hitting set problem for several range spaces considered in [3].
- 3.
We give a for weighted version of Problem 2 by using sweep-line method (see Section 4).
- 4.
We further show that Problem 2 is -hard for with rectangles intersecting a strip (see Section 5).
Section snippets
- is -hard
We start this section with the definition of the vertex cover problem. Let be an undirected graph where V is the set of vertices and E is the set of edges. We say a subset covers an edge if at least one endpoint of e is in . In the vertex cover problem, the goal is to find a minimum size subset which covers all edges in E. The vertex cover problem is known to be -hard on cubic graphs [1].
Chan and Grant [3] define an -hard set cover problem - and use it to
-hardness results
Chan and Grant [3] show -hardness of geometric set cover problem for a list of ten different geometric set systems. However, they prove -hardness of geometric hitting set for only four out of these ten set systems. In this section, we show how to prove the -hardness of geometric hitting set for the remaining six problems.
We now list the geometric set systems for which -hardness of geometric set cover is proven but the -hardness of geometric hitting set is not addressed by Chan
for Rect-Hit-Bounded problem
In one of our recent papers [11], we give a for weighted set cover problem with rectangles in the plane where for a constant C. In this section, we give a for weighted version of Rect-Hit-Bounded. Our algorithm is inspired from [4] and the for set cover problem [11].
Let be an instance of Rect-Hit-Bounded problem where all rectangles in are inside a rectangular box T of size for some integer constant t. Let be the unit grid partition
NP-hardness of Rect-Hit-Bounded problem
Let H be the strip in the plane bounded by and . We now show that Problem 2 is -hard when all rectangles in intersect H. The proof uses ideas in [7], [10], [11]. We now give the outline of the proof.
We give a polynomial time reduction from a known -hard problem, vertex cover on planar graphs where degree of every vertex is less than or equal to three [8]. Let be the given graph such that it is planar and every vertex in V is incident on at most three edges in E. Further,
References (13)
- et al.
Some APX-completeness results for cubic graphs
Theor. Comput. Sci.
(2000) - et al.
Exact algorithms and APX-hardness results for geometric packing and covering problems
Comput. Geom.
(February 2014) - et al.
Geometric red blue set cover for unit squares and related problems
Comput. Geom.
(2015) - et al.
Optimal packing and covering in the plane are NP-complete
Inf. Process. Lett.
(1981) - et al.
The within-strip discrete unit disk cover problem
Theor. Comput. Sci.
(2017) - et al.
Optimization, approximation, and complexity classes
J. Comput. Syst. Sci.
(1991)
Cited by (2)
Exact Algorithms and Hardness Results for Geometric Red-Blue Hitting Set Problem
2022, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Hardness results and approximation schemes for discrete packing and domination problems
2018, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- 1
Partially supported by grant No. SB/FTP/ETA-434/2012 under DST-SERB Fast Track Scheme for Young Scientist.