Introduction
In computational geometry, managing axis-parallel rectangles is a foundational task with applications ranging from VLSI design to map labeling. Two central optimization problems in this domain are the Maximum Independent Set (MIS)—finding the largest collection of non-overlapping rectangles—and the Minimum Hitting Set (MHS)—finding the smallest set of points that intersects every rectangle in a given family.
While these problems are NP-hard for general rectangles, researchers often look for restricted settings that remain theoretically interesting yet computationally tractable. This paper investigates "diagonal-intersecting families," where every rectangle must intersect a common diagonal line (e.g., $y = -x$). This constraint serves as a critical stepping stone toward resolving broader questions like Wegner’s Conjecture, which posits that the "duality gap"—the ratio between the sizes of the MHS and the MIS—is bounded by a small constant.
Complexity and the Boundary of Hardness
The authors identify a sharp transition in computational complexity based on how rectangles relate to the diagonal.
- Diagonal-Lower-Intersecting: If rectangles intersect the diagonal but are restricted to the region below it, the problem is solvable in polynomial time.
- General Diagonal-Intersecting: If rectangles can cross the diagonal to both sides, the MIS problem becomes NP-complete.
To prove NP-completeness for the general case, the researchers employed a reduction from Planar 3-SAT. They constructed complex "gadgets"—variable and clause components made of rectangles—that mimic logical operations. This demonstrates that even with the diagonal constraint, the structural complexity of rectangle overlaps can encode hard logical problems.
The Harpoon Algorithm
For the tractable "diagonal-lower-intersecting" subclass, the paper introduces a significant algorithmic improvement. Previous solutions required $O(n^3)$ time. The authors developed a dynamic programming approach that achieves $O(n^2)$ time by utilizing a geometric structure they call a harpoon.
A harpoon is a specific region defined by a pair of rectangles. By calculating optimal solutions for these regions and leveraging amortized analysis, the authors show that the cost of computing solutions across all harpoons is effectively constant per rectangle, leading to the quadratic speedup. This algorithm also extends to the Maximum Weight Independent Set (WMIS) problem, where each rectangle has an associated value.
Tightening the Duality Gap
A major contribution of this work is the refinement of the duality gap for diagonal-intersecting families. The duality gap represents the efficiency of hitting sets relative to independent sets.
- Previous Bounds: The best-known upper bound for the duality gap in this class was 6.
- New Bounds: The authors improved this upper bound to 4. They also established a lower bound of 2 by exhibiting specific rectangle families (such as the "doubled 6-cycle") where the hitting set must be at least twice the size of the independent set.
These results are summarized across different subclasses:
- Diagonal-touching: Gap between 1.5 and 2.
- Diagonal-lower-intersecting: Gap between 2 and 3.
- General diagonal-intersecting: Gap between 2 and 4.
Conclusion
This research clarifies the algorithmic landscape for rectangles constrained by a diagonal line. By providing an $O(n^2)$ algorithm for the lower-intersecting case and proving NP-completeness for the general case, the authors delineate the limits of efficiency. Furthermore, tightening the duality gap to a factor of 4 brings us closer to understanding Wegner’s Conjecture. Future work remains in determining the exact complexity of the Minimum Hitting Set problem for these classes and developing methods to recognize the intersection graphs of these geometric families.
Summary updated