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(n1+δ) time for an arbitrarily small constant δ>0. This significantly improves the previous O(loglog n)-approximation algorithm by Agarwal, Har-Peled, Raychaudhury, and Sintos (SODA~2024), which ran in O(nd/2mathoprm 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 ℝ2 and achieved only O(√nmathoprm polylog n) amortized expected update time. * For n axis-aligned rectangles in ℝ2, we give an O(1)-approximation algorithm for MIS that runs in O(n1+δ) time. Our result significantly improves the running time of the celebrated algorithm by Mitchell (FOCS~2021) (which was about O(n21)), 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. * For disks in ℝ2 or hypercubes in any constant dimension, we give the first fully dynamic (1+varepsilon)-approximation algorithms for MVC and MCM with O(mathoprm polylogn) amortized update time.