Enclosing Points with Geometric Objects

Let X be a set of points in R² and O be a set of geometric objects in R², where |X| + |O| = n. We study the problem of computing a minimum subset O^* ⊆ O that encloses all points in X. Here a point x ∈ X is enclosed by O^* if it lies in a bounded connected component of R² (O ∈ O^* O). We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in $O(1)$-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an O(α(n)log n)-approximation algorithm for segments, where α(n) is the inverse Ackermann function, and an O(log n)-approximation algorithm for disks.