Approximation Algorithms for Geometric Packing and Covering Problems

Abstract

We study a host of geometric optimization problems that are NP-hard and design polynomial time approximation algorithms for them. More precisely, we are given a family of geometric objects and a point set, mostly in the plane, and study different variants and generalizations of Packing and Covering problems. Our objects of study are mostly family of non-piercing regions in the plane. We call a set of simple and connected regions to be non-piercing if for any pair of intersecting regions, A and B both A\B and B\A are connected regions. A set of disks, squares, half-planes are examples of non-piercing regions, whereas, a set of lines, rectangles are examples of piercing objects. For most of the problems we have studied, a simple local search algorithm is enough to yield a PTAS whose analysis of approximation requires a suitable bipartite graph on the local search solution and the optimal solution to have a balanced sub-linear separator. We study a generalization of the standard packing problem, called the Capacitated Region Packing problem and its slight variant, the Shallow Packing problem. We devise a PTAS for both these problems with restrictions on the capacities. For the former problem, the objects are non-piercing whereas for the latter problem the objects can be even more general and only have sub-quadratic union complexity with the capacities at most some constant for both the cases. The non-triviality here is to show that the intersection graph of arrangements with shallow depth, which is not planar, has balanced sub-linear separators. Our results complement the Maximum Independent Set of Rectangles problem as rectangles are both piercing and have quadratic union complexity. We also study the Shallow Point Packing problem and are able to show that local search works here as well for unit capacity and devise a constant factor approximation algorithm using an adaptation Brannaman-Goodrich technique for packing problems. Runaway Rectangle Escape problem is closely related to the above packing problems and is motivated from routing in printed circuit boards. Here we are given a set of axis-parallel rectangles inside a rectangular boundary R and a maximum allowed depth d. The objective is to extend the maximum number of input rectangles to one of the four sides of R such that the maximum depth of a point is at most d after extension. We show that local search gives a (2 + )-approximation for d = O(1). When the input rectangles are all disjoint then we devise a simple 4(1 + 1=(d ð€€€ 1))-approximation algorithm. We also propose a randomized (1 + )-approximation algorithm based on randomized rounding making some density assumptions. Lastly, we show the problem to be NP-hard even when the rectangles are unit squares aligned in a grid. We study the Multi-Cover problem which is a generalization of the Set Cover problem. We give a PTAS for non-piercing regions when the depth of every point is at most constant. We also study different variants of the covering problem like the Unique Coverage, and Prize Collecting Set Cover problem. For Unique Cover we show that local search yields a PTAS for non-piercing regions for bounded depth and degree. For Prize Collecting Set Cover a PTAS works for non-piercing regions if the weight of every region is within a range [1; a], where a is some constant. Lastly, we consider variants of the Art Gallery problems called the Minimum (Horizontal) Sliding Cameras problem, M(H)SC. We are given an orthogonal polygon and we need to deploy mobile guards who can walk along an orthogonal (horizontal) line segment and can guard a point inside the polygon if the perpendicular drawn from the point onto the line segment lies inside the polygon. Our local search algorithm yields a PTAS for the MHSC problem and also the MSC problem when the polygon has no holes. In order to do so we prove an appropriate graph on orthogonal line segments to be planar by proposing a graph drawing scheme.