{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:53:05Z","timestamp":1783036385550,"version":"3.54.6"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T00:00:00Z","timestamp":1560729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004836","name":"Danish Council for Independent Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217462"],"award-info":[{"award-number":["CCF-1217462"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>\n            We present a (1+\u03b5)-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\u00a0\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03b5<\/jats:sup>\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.,\n            <jats:italic>K<\/jats:italic>\n            <jats:sub>2,2<\/jats:sub>\n            ). 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.\n          <\/jats:p>\n          <jats:p>\n            For the case of large axis-parallel rectangles, we provide a\n            <jats:italic>polynomial<\/jats:italic>\n            time (1 + \u03b5)-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.\n          <\/jats:p>","DOI":"10.1145\/3326122","type":"journal-article","created":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T12:14:26Z","timestamp":1560860066000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Approximation Schemes for Independent Set and Sparse Subsets of Polygons"],"prefix":"10.1145","volume":"66","author":[{"given":"Anna","family":"Adamaszek","sequence":"first","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[{"name":"University of Illinois Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[{"name":"Universidad de Chile, Santiago Centro, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00028-5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1143176.1646569"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.50"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA). 400--409","author":"Adamaszek A.","unstructured":"A. Adamaszek and A. Wiese . 2014. A QPTAS for maximum weight independent set of polygons with polylogarithmic many vertices . In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA). 400--409 . A. Adamaszek and A. Wiese. 2014. A QPTAS for maximum weight independent set of polygons with polylogarithmic many vertices. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA). 400--409."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Adamaszek A.","unstructured":"A. Adamaszek and A. Wiese . 2015. A quasi-PTAS for the two-dimensional geometric knapsack problem . In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915) . SIAM, 1491--1505. A. Adamaszek and A. Wiese. 2015. A quasi-PTAS for the two-dimensional geometric knapsack problem. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). SIAM, 1491--1505."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Bandyapadhyay S.","unstructured":"S. Bandyapadhyay , S. Bhowmick , and K. R. Varadarajan . 2015. Approximation schemes for partitioning: Convex decomposition and surface approximation . In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915) . SIAM, 1457--1470. S. Bandyapadhyay, S. Bhowmick, and K. R. Varadarajan. 2015. Approximation schemes for partitioning: Convex decomposition and surface approximation. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). SIAM, 1457--1470."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1188"},{"key":"e_1_2_1_10_1","first-page":"115","article-title":"On approximation properties of the independent set problem for low degree graphs. Theo","volume":"32","author":"Berman P.","year":"1999","unstructured":"P. Berman and T. Fujito . 1999 . On approximation properties of the independent set problem for low degree graphs. Theo . Comp. Sci. 32 , 2 (1999), 115 -- 132 . P. Berman and T. Fujito. 1999. On approximation properties of the independent set problem for low degree graphs. Theo. Comp. Sci. 32, 2 (1999), 115--132.","journal-title":"Comp. Sci."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000210"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.10"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 892--901","author":"Chalermsook P.","unstructured":"P. Chalermsook and J. Chuzhoy . 2009. Maximum independent set of rectangles . In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 892--901 . P. Chalermsook and J. Chuzhoy. 2009. Maximum independent set of rectangles. In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 892--901."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Chuzhoy J.","unstructured":"J. Chuzhoy and A. Ene . 2016. On approximating maximum independent set of rectangles . In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201916) . 820--829. J. Chuzhoy and A. Ene. 2016. On approximating maximum independent set of rectangles. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201916). 820--829."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122778"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116657.3116973"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189314"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00294-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115953.3115999"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"L. de Floriani P. Magillo and Puppo E. 2000. Applications of computational geometry to geographic information systems. In Handbook of Computational Geometry J.-R. Sack and J. Urrutia (Eds.). North Holland Amsterdam 333--388.  L. de Floriani P. Magillo and Puppo E. 2000. Applications of computational geometry to geographic information systems. In Handbook of Computational Geometry J.-R. Sack and J. Urrutia (Eds.). North Holland Amsterdam 333--388.","DOI":"10.1016\/B978-044482537-7\/50008-5"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261253"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402676"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/383891.383893"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.06.002"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 1161--1165","author":"Fox J.","unstructured":"J. Fox and J. Pach . 2011. Computing the independence number of intersection graphs . In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 1161--1165 . J. Fox and J. Pach. 2011. Computing the independence number of intersection graphs. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 1161--1165."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799350232"},{"key":"e_1_2_1_30_1","volume-title":"Being fat and friendly is not enough. CoRR abs\/0908.2369","author":"Har-Peled S.","year":"2009","unstructured":"S. Har-Peled . 2009. Being fat and friendly is not enough. CoRR abs\/0908.2369 ( 2009 ). S. Har-Peled. 2009. Being fat and friendly is not enough. CoRR abs\/0908.2369 (2009)."},{"key":"e_1_2_1_31_1","volume-title":"Geometric Approximation Algorithms. Mathematical Surveys and Monographs","author":"Har-Peled S.","unstructured":"S. Har-Peled . 2011. Geometric Approximation Algorithms. Mathematical Surveys and Monographs , Vol. 173 . American Mathematical Society, Boston , MA. S. Har-Peled. 2011. Geometric Approximation Algorithms. Mathematical Surveys and Monographs, Vol. 173. American Mathematical Society, Boston, MA."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582157"},{"key":"e_1_2_1_33_1","first-page":"19","article-title":"Shortest path in a polygon using sublinear space","volume":"7","author":"Har-Peled S.","year":"2016","unstructured":"S. Har-Peled . 2016 . Shortest path in a polygon using sublinear space . J. Comput. Geom. 7 , 2 (2016), 19 -- 45 . http:\/\/jocg.org\/index.php\/jocg\/article\/view\/256. S. Har-Peled. 2016. Shortest path in a polygon using sublinear space. J. Comput. Geom. 7, 2 (2016), 19--45. http:\/\/jocg.org\/index.php\/jocg\/article\/view\/256.","journal-title":"J. Comput. Geom."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1017"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90012-3"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.11.003"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA). 384--393","author":"Khanna S.","unstructured":"S. Khanna , S. Muthukrishnan , and M. Paterson . 1998. On approximating rectangle tiling and packing . In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA). 384--393 . S. Khanna, S. Muthukrishnan, and M. Paterson. 1998. On approximating rectangle tiling and packing. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA). 384--393."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"L.\n      Lewin-Eytan J.\n      Naor and \n      A.\n      Orda\n  . \n  2002\n  . Routing and admission control in networks with advance reservations. In Proceedings of the 5th International Conference on \n  Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u2019\n  02) Lecture Notes in Computer Science Vol. \n  2462\n  . 215--228.  L. Lewin-Eytan J. Naor and A. Orda. 2002. Routing and admission control in networks with advance reservations. In Proceedings of the 5th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201902) Lecture Notes in Computer Science Vol. 2462. 215--228.","DOI":"10.1007\/3-540-45753-4_19"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 13th IEEE International Conference on Data Engineering. IEEE, 220--231","author":"Lent B.","unstructured":"B. Lent , A. Swami , and J. Widom . 1997. Clustering association rules . In Proceedings of the 13th IEEE International Conference on Data Engineering. IEEE, 220--231 . B. Lent, A. Swami, and J. Widom. 1997. Clustering association rules. In Proceedings of the 13th IEEE International Conference on Data Engineering. IEEE, 220--231."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000400"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90030-9"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 23nd Annual Euro. Symposium Algorithms (ESA). Lecture Notes in Computer Science","volume":"9294","author":"Marx D.","unstructured":"D. Marx and M. Pilipczuk . 2015. Optimal parameterized algorithms for planar facility location problems using voronoi diagrams . In Proceedings of the 23nd Annual Euro. Symposium Algorithms (ESA). Lecture Notes in Computer Science , Vol. 9294 . Springer, Berlin, 865--877. D. Marx and M. Pilipczuk. 2015. Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. In Proceedings of the 23nd Annual Euro. Symposium Algorithms (ESA). Lecture Notes in Computer Science, Vol. 9294. Springer, Berlin, 865--877."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.64"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00336-3"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884537"},{"key":"e_1_2_1_48_1","unstructured":"M. Sharir and P. K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press New York.   M. Sharir and P. K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press New York."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005527"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 232--243","author":"Smith W. D.","unstructured":"W. D. Smith and N. C. Wormald . 1998. Geometric separator theorems and applications . In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 232--243 . W. D. Smith and N. C. Wormald. 1998. Geometric separator theorems and applications. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 232--243."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 7th Annual European Symposium Algorithms (ESA). 426--437","author":"Verweij B.","unstructured":"B. Verweij and K. Aardal . 1999. An optimisation algorithm for maximum independent set with applications in map labelling . In Proceedings of the 7th Annual European Symposium Algorithms (ESA). 426--437 . B. Verweij and K. Aardal. 1999. An optimisation algorithm for maximum independent set with applications in map labelling. In Proceedings of the 7th Annual European Symposium Algorithms (ESA). 426--437."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326122","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3326122","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3326122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:08Z","timestamp":1750204388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,17]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3326122"],"URL":"https:\/\/doi.org\/10.1145\/3326122","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,17]]},"assertion":[{"value":"2018-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}