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²\(^S_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.