text: The Maximum Weight Independent Set of Polygons problem is a fundamental problem in computational geometry. Given a set of weighted polygons in the 2-dimensional plane, the goal is to find a set of pairwise non-overlapping polygons with maximum total weight. Due to its wide range of applications, the MWISP problem and its special cases have been extensively studied both in the approximation algorithms and the computational geometry community. Despite a lot of research, its general case is not well-understood. Currently the best known polynomial time algorithm achieves an approximation ratio of n^(epsilon) [Fox and Pach, SODA 2011], and it is not even clear whether the problem is APX-hard. We present a (1+epsilon)-approximation algorithm, assuming that each polygon in the input has at most a polylogarithmic number of vertices. Our algorithm has quasi-polynomial running time. We use a recently introduced framework for approximating maximum weight independent set in geometric intersection graphs. The framework has been used to construct a QPTAS in the much simpler case of axis-parallel rectangles. We extend it in two ways, to adapt it to our much more general setting. First, we show that its technical core can be reduced to the case when all input polygons are triangles. Secondly, we replace its key technical ingredient which is a method to partition the plane using only few edges such that the objects stemming from the optimal solution are evenly distributed among the resulting faces and each object is intersected only a few times. Our new procedure for this task is not more complex than the original one, and it can handle the arising difficulties due to the arbitrary angles of the polygons. Note that already this obstacle makes the known analysis for the above framework fail. Also, in general it is not well understood how to handle this difficulty by efficient approximation algorithms.
  @cite_18: We study the Maximum Independent Set of Rectangles (MISR) problem: given a collection R of n axis-parallel rectangles, find a maximum-cardinality subset of disjoint rectangles. MISR is a special case of the classical Maximum Independent Set problem, where the input is restricted to intersection graphs of axis-parallel rectangles. Due to its many applications, ranging from map labeling to data mining, MISR has received a significant amount of attention from various research communities. Since the problem is NP-hard, the main focus has been on the design of approximation algorithms. Several groups of researches have independently suggested O(log n)-approximation algorithms for MISR, and this remained the best currently known approximation factor for the problem. The main result of our paper is an O(log log n)-approximation algorithm for MISR. Our algorithm combines existing approaches for solving special cases of the problem, in which the input set of rectangles is restricted to containing specific intersection types, with new insights into the combinatorial structure of sets of intersecting rectangles in the plane. We also consider a generalization of MISR to higher dimensions, where rectangles are replaced by d-dimensional hyper-rectangles. Our results for MISR imply an O((log n)d−2 log log n)-approximation algorithm for this problem, improving upon the best previously known O((log n)d−1)-approximation.
  @cite_4: 
  @cite_8: In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g. in data mining, map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1 + e)-approximation algorithm for the MWISR problem with quasipolynomial running time 2poly(log n e). In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(log log n) (unweighted case) and O(log n log log n) (weighted case). Key to our results is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. In particular, we present a method of partitioning the plane into small and simple areas such that the rectangles of an optimal solution are intersected in a very controlled manner. Together with a novel application of the weighted planar graph separator theorem due to [4] this allows us to upper bound our approximation ratio by 1 + e. Our dynamic program is very general and we believe that it will be useful for other settings. In particular, we show that, when parametrized properly, it provides a polynomial time (1 + e)-approximation for the special case of the MWISR problem when each rectangle is relatively large in at least one dimension. Key to this analysis is a method to tile the plane in order to approximately describe the topology of these rectangles in an optimal solution. This technique might be a useful insight to design better polynomial time approximation algorithms or even a PTAS for the MWISR problem. In particular, note that our results imply that the MWISR problem is not APX-hard, unless NP ⊆ DTIME(2polylog (n)).
  @cite_21: 
  @cite_23: Our study of tiling and packing with rectangles in two-dimensional regions is strongly motivated by applications in database mining, histogram-based estimation of query sizes, data partitioning, and motion estimation in video compression by block matching, among others. An example of the problems that we tackle is the following: given an n by n array A of positive numbers, find a tiling using at most p rectangles (that is, no two rectangles must overlap, and each array element must fall within some rectangle) that minimizes the maximum weight of any rectangle; here the "weight" of a rectangle is the sum of the array elements that fall within it. If the array A were one-dimensional, this problem could be easily solved by dynamic programming. We prove that in the two-dimensional case it is NP-hard to approximate this problem to within a factor of 1.25. On the other hand, we provide a near-linear time algorithm that returns a solution at most 2.5 times the optimal. Other rectangle tiling and packing problems that we study have similar properties: while it is easy to solve them optimally in one dimension, the two-dimensional versions become NP-hard. We design efficient approximation algorithms for these problems.
  @cite_20: Abstract We present in this paper a simple yet efficient algorithm for stabbing a set S of n axis-parallel boxes in d -dimensional space with c( S ) points in output-sensitive time O (dn log c( S )) and linear space. Let c ∗ ( S ) and b ∗ ( S ) be, respectively, the minimum number of points required to stab S and the maximum number of pairwise disjoint boxes of S . We prove that b ∗ ( S )⩽c ∗ ( S )⩽c( S )⩽b ∗ ( S )(1+ log 2 b ∗ ( S )) d−1 . Since finding a minimal set of c ∗ ( S ) points is NP-complete as soon as d>1 , we obtain a fast precision-sensitive heuristic for stabbing S whose quality does not depend on the input size. In the case of congruent or constrained isothetic boxes, our algorithm reports, respectively, c( S )⩽2 d−1 b ∗ ( S ) and c( S )=O d (b ∗ ( S )) stabbing points. Moreover, we show that the bounds we get on c( S ) are asymptotically tight and corroborate our results with some experiments. We also describe an optimal output-sensitive algorithm for finding a minimal-size optimal stabbing point-set of intervals. Finally, we conclude with insights for further research.
  @cite_17: Motivated by the problem of labeling maps, we investigate the problem of computing a large non-intersecting subset in a set of n rectangles in the plane. Our results are as follows. In O(n log n) time, we can find an O(log n)factor approximation of the maximum subset in a set of n arbitrary axis-parallel rectangles in the plane. If all rectangles have unit height, we can find a 2-approximation in O(n logn) time. Extending this result, we obtain a (1 + l k)-approximati on in time O(n logn + n 2k-1) time, for any integer k > 1. © 1998 Elsevier Science B.V. All rights reserved.
summary: When going beyond the fat objects, the problem becomes much less understood. Even for axis-parallel rectangles the best known polynomial time algorithms are @math -approximation for weighted case due to Chan and Har-Peled @cite_21 , and a @math -approximation for unweighted case by Chalermsook and Chuzhoy @cite_18 . Prior to the latter results, many @math -approximation algorithms have been found @cite_17 @cite_4 @cite_23 @cite_20 . Very recently, a QPTAS has been presented @cite_8 .