Approximation Schemes for Independent Set and Sparse Subsets of Polygons
Open Access
- 17 June 2019
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 66 (4) , 1-40
Abstract
We present a (1+ε)-approximation algorithm with quasi-polynomial running time for computing a maximum weight independent set of polygons from a given set of polygons in the plane. Contrasting this, the best-known polynomial time algorithm for the problem has an approximation ratio of n ε . Surprisingly, we can extend the algorithm to the problem of computing the maximum cardinality subset of the given set of polygons whose intersection graph fulfills some sparsity condition. For example, we show that one can approximate the maximum subset of polygons such that the intersection graph of the subset is planar or does not contain a cycle of length 4 (i.e., K 2,2 ). Our algorithm relies on a recursive partitioning scheme, whose backbone is the existence of balanced cuts with small complexity that intersect polygons from the optimal solution of a small total weight. For the case of large axis-parallel rectangles, we provide a polynomial time (1 + ε)-approximation for the maximum weight independent set. Specifically, we consider the problem where each rectangle has one edge whose length is at least a constant fraction of the length of the corresponding edge of the bounding box of all the input elements. This is now the most general case for which a PTAS is known, and it requires a new and involved partitioning scheme, which should be of independent interest.Keywords
All Related Versions
Funding Information
- Danish Council for Independent Research
- National Science Foundation (CCF-1217462)
This publication has 31 references indexed in Scilit:
- Separator theorems and Turán-type results for planar intersection graphsAdvances in Mathematics, 2008
- Polynomial-time approximation schemes for packing and piercing fat objectsJournal of Algorithms, 2003
- Efficient Approximation Algorithms for Tiling and Packing Problems with RectanglesJournal of Algorithms, 2001
- Data Mining with optimized two-dimensional association rulesACM Transactions on Database Systems, 2001
- Label placement by maximum independent set in rectanglesComputational Geometry, 1998
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a WalkJournal of Algorithms, 1995
- Finding small simple cycle separators for 2-connected planar graphsJournal of Computer and System Sciences, 1986
- Approximation schemes for covering and packing problems in image processing and VLSIJournal of the ACM, 1985
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the planeJournal of Algorithms, 1983