Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching

We develop simple and general techniques to obtain faster (near-linear time) static approximation algorithms, as well as efficient dynamic data structures, for four fundamental geometric optimization problems: minimum piercing set (MPS), maximum independent set (MIS), minimum vertex cover (MVC), and maximum-cardinality matching (MCM). Highlights of our results include the following:

• For n axis-aligned boxes in any constant dimension d, we give an O(log log n)-approximation algorithm for MPS that runs in O(n 1+δ ) time for an arbitrarily small constant δ > 0. This significantly improves the previous O(log log n)-approximation algorithm by Agarwal, Har-Peled, Raychaudhury, and Sintos (SODA 2024), which ran in O(n d/2 polylog n) time.

• Furthermore, we show that our algorithm can be made fully dynamic with O(n δ ) amortized update time. Previously, Agarwal et al. (SODA 2024) obtained dynamic results only in R 2 and achieved only O( √ n polylog n) amortized expected update time.

• For n axis-aligned rectangles in R 2 , we give an O(1)-approximation algorithm for MIS that runs in O(n 1+δ ) time. Our result significantly improves the running time of the celebrated algorithm by Mitchell (FOCS 2021) (which was about O(n 21 )), and answers one of his open questions. Our algorithm can also be made fully dynamic with O(n δ ) amortized update time.

• For n (unweighted or weighted) fat objects in any constant dimension, we give a dynamic O(1)-approximation algorithm for MIS with O(n δ ) amortized update time. Previously, Bhore, N öllenburg, T óth, and Wulms (SoCG 2024) obtained efficient dynamic O(1)-approximation algorithms only for disks in R 2 and only in the unweighted setting.

• For n axis-aligned rectangles in R 2 , we give a dynamic ( 3 2 + ε)-approximation algorithm for MVC with O(polylog n) amortized update time for any constant ε > 0. Our static result improves the running time of Bar-Yehuda, Hermelin, and Rawitz (2011). For disks in R 2 or hypercubes in any constant dimension, we give the first fully dynamic (1 + ε)approximation algorithm for MVC with O(polylog n) amortized update time.

• For (monochromatic or bichromatic) disks in R 2 or hypercubes in any constant dimension, we give the first fully dynamic (1 + ε)-approximation algorithm for MCM with O(polylog n) amortized update time.