2026-07-21T08:18:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20006 2024-06-06T06:21:16Z ddc:004 open_access

Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions Grandoni, Fabrizio Husić, Edin Mari, Mathieu Tinguely, Antoine Approximation algorithms packing independent set polygons In the maximum independent set of convex polygons problem, we are given a set of n convex polygons in the plane with the objective of selecting a maximum cardinality subset of non-overlapping polygons. Here we study a special case of the problem where the edges of the polygons can take at most d fixed directions. We present an 8d/3-approximation algorithm for this problem running in time O((nd)^O(d4^d)). The previous-best polynomial-time approximation (for constant d) was a classical n^ε approximation by Fox and Pach [SODA'11] that has recently been improved to a OPT^ε-approximation algorithm by Cslovjecsek, Pilipczuk and Węgrzycki [SODA '24], which also extends to an arbitrary set of convex polygons. Our result builds on, and generalizes the recent constant factor approximation algorithms for the maximum independent set of axis-parallel rectangles problem (which is a special case of our problem with d = 2) by Mitchell [FOCS'21] and Gálvez, Khan, Mari, Mömke, Reddy, and Wiese [SODA'22]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fabrizio Grandoni and Edin Husić and Mathieu Mari and Antoine Tinguely 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.61 urn:nbn:de:0030-drops-200066 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.61 eng https://creativecommons.org/licenses/by/4.0/legalcode