New approximation methods for geometric optimization with limited piercing
Geometric Optimization Parameterized by Piercing Complexity
Computational GeometryData Structures and Algorithms
Summary
Packing and covering shapes on a plane is a basic problem in computer science, but it's usually hard to find the best solutions quickly. The paper looks at a property called piercing degree, which measures how many shapes can split another shape apart. The authors show that when this piercing degree is limited, standard local search methods can find very close-to-best solutions efficiently for common problems like independent set and set cover. They also provide approximation guarantees for weighted versions of these problems, extending previous results.
What this means in practice
- •For computational geometry developers: Design efficient approximation algorithms for packing and covering problems with complex shapes but limited piercing interactions.
- •For spatial data analysts: Improve heuristic methods for selecting non-overlapping regions in spatial data sets where shapes interact mildly by piercing.
A theory result. No direct application yet.
Authors
Aritra Banik, Rajiv Raman, Saurabh Ray
Abstract
Packing and covering problems for geometric regions have been studied under many notions of complexity, including VC-dimension, union complexity, shallow-cell complexity, and fatness. Although these restrictions often yield constant-factor approximation algorithms, they do not by themselves generally lead to PTASs. A recurring feature of known hardness constructions is that one region may be \emph{pierced} by many others: a region $B$ pierces $A$ when $A\setminus B$ is disconnected. We study geometric instances through the \emph{piercing degree}. Since piercing is symmetric for Jordan regions, this is the maximum degree of the corresponding piercing graph. Our main result is that, for every fixed piercing degree, the standard local-search algorithms give PTASs for the unweighted \emph{Discrete Independent Set} and \emph{Set Cover} problems. The proof constructs a sublinear balanced separator for an appropriate locality graph and applies it adaptively throughout the recursive local-search analysis. This guarantee depends only on the piercing degree; in particular, it places no bound on the number of components created by an individual piercing pair. We also prove a polynomial shallow-trace bound depending only on the piercing degree. As consequences, for every fixed piercing degree, weighted Set Cover admits a deterministic $C_r$-approximation and weighted Discrete Independent Set admits a deterministic $O(r+1)$-approximation. These results extend the known guarantees for non-piercing families and apply, for example, to axis-parallel rectangles when every rectangle is pierced by only a bounded number of other rectangles.