Approximability and hardness of geometric hitting set with axis-parallel rectangles

https://doi.org/10.1016/j.ipl.2018.09.003Get rights and content

Highlights

  • A new APX-hard hitting set problem SPECIAL-3HS is introduced.

  • By using SPECIAL-3HS, we prove APX-hardness of hitting set for rectangles with a common point.

  • We give a PTAS for weighted hitting set with bounded integer side length rectangles.

  • We show that hitting set is NP-hard even when all rectangles are of size 1×2 and 2×1 and intersect y=1 or y=2.

Abstract

We show that geometric hitting set with axis-parallel rectangles is APX-hard even when all rectangles share a common point. We also show that geometric hitting set problem is APX-hard for several classes of objects given in [3] such as axis-parallel ellipses with a shared point, axis-parallel cubes sharing a common point, etc.

Further, we give a polynomial time approximation scheme (PTAS) for the weighted hitting set problem with axis-parallel rectangles when all rectangles have integer side lengths bounded by a constant C. Finally, we show that the problem is NP-hard for rectangles of size 1×2 and 2×1 even when every rectangle intersects a given unit height horizontal strip.

Introduction

Let P be a set of points and O be a set of objects in the plane. We say that a subset PP is a hitting set for O if every object in O contains at least one point in P. In the hitting set problem, we are given (P,O) and the goal is to find a minimum size hitting set PP of points for objects in O. In weighted version of the problem, every point pP is given a non-negative weight Wp and the goal is to find a hitting set PP for O with minimum ΣpPWp. In this paper, we consider the following two hitting set problems.

Problem 1

Rect-Hit. All the objects in O 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 NP-hard when O 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 APX-hard [3] even for two types of rectangles. The best-known approximation factor for hitting set with axis-parallel rectangles is O(loglogn) [2].

Bounded side length axis-parallel rectangles. The hitting set problem is known to be NP-hard for unit squares [6]. However, three PTASes are known for the hitting set problem with unit squares, one in unweighted case [12] and two by duality from PTASes for weighted set cover [5], [4].

For objects in Problem 2, a PTAS is known for set cover problem [11]. However, as our objects are not unit squares, this does not give a PTAS for Problem 2 by duality.

The major contributions of the paper are as follows:

  • 1.

    We define a special hitting set problem SPECIAL-3HS and show that it is APX hard (see Section 2).

  • 2.

    We prove that Problem 1 is APX-hard even when origin in the plane is inside all rectangles by giving a reduction from SPECIAL-3HS (see Section 3). We use SPECIAL-3HS to prove APX-hardness of hitting set problem for several range spaces considered in [3].

  • 3.

    We give a PTAS for weighted version of Problem 2 by using sweep-line method (see Section 4).

  • 4.

    We further show that Problem 2 is NP-hard for C=2 with rectangles intersecting a strip {(x,y)|1y2} (see Section 5).

Section snippets

SPECIAL-3HS is APX-hard

We start this section with the definition of the vertex cover problem. Let G=(V,E) be an undirected graph where V is the set of vertices and E is the set of edges. We say a subset VV covers an edge eE if at least one endpoint of e is in V. In the vertex cover problem, the goal is to find a minimum size subset VV which covers all edges in E. The vertex cover problem is known to be APX-hard on cubic graphs [1].

Chan and Grant [3] define an APX-hard set cover problem SPECIAL-3SC and use it to

APX-hardness results

Chan and Grant [3] show APX-hardness of geometric set cover problem for a list of ten different geometric set systems. However, they prove APX-hardness of geometric hitting set for only four out of these ten set systems. In this section, we show how to prove the APX-hardness of geometric hitting set for the remaining six problems.

We now list the geometric set systems for which APX-hardness of geometric set cover is proven but the APX-hardness of geometric hitting set is not addressed by Chan

PTAS for Rect-Hit-Bounded problem

In one of our recent papers [11], we give a PTAS for weighted set cover problem with rectangles [a,b]×[c,d] in the plane where ba,dc{1,2,,C} for a constant C. In this section, we give a PTAS for weighted version of Rect-Hit-Bounded. Our algorithm is inspired from [4] and the PTAS for set cover problem [11].

Let (PT,OT) be an instance of Rect-Hit-Bounded problem where all rectangles in OT are inside a rectangular box T of size t×t for some integer constant t. Let Z be the unit grid partition

NP-hardness of Rect-Hit-Bounded problem

Let H be the strip in the plane bounded by y=1 and y=2. We now show that Problem 2 is NP-hard when all rectangles in O 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 NP-hard problem, vertex cover on planar graphs where degree of every vertex is less than or equal to three [8]. Let G0=(V,E) 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)

There are more references available in the full text version of this article.

Cited by (2)

1

Partially supported by grant No. SB/FTP/ETA-434/2012 under DST-SERB Fast Track Scheme for Young Scientist.

View full text