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). 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) n) -approximation algorithm for segments, where (n) is the inverse Ackermann function, and an O (n) -approximation algorithm for disks.