Key points are not available for this paper at this time.
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 (n) -approximation algorithm for MPS that runs in O (n^1+) time for an arbitrarily small constant >0. This significantly improves the previous O (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² and achieved only O (n polylog n) amortized expected update time. * For n axis-aligned rectangles in R², 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. * For disks in R² or hypercubes in any constant dimension, we give the first fully dynamic (1+) -approximation algorithms for MVC and MCM with O (polylogn) amortized update time.
Bhore et al. (Tue,) studied this question.