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

arXiv: https://arxiv.org/abs/2407.20659 · HTML: https://mlsanity.com/paper/2407.20659/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2024.

## Built on by (most cited first, 3 of 3)

- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Online Epsilon Net and Piercing Set for Geometric Concepts](https://mlsanity.com/paper/2410.07059/) (2024)

## Abstract (arXiv)

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.