Separating Points By Axis-Parallel Lines
Abstract
We study the problem of separating n points in the plane, no two of which have the same x- or y-coordinate, using a minimum number of vertical and horizontal lines avoiding the points, so that each cell of the subdivision contains at most one point. We prove that this problem and some variants of it are APX-hard. We give a 2-approximation algorithm, and a $d$-approximation algorithm for the $d$-dimensional variant, in which the points are to be separated using axis-parallel hyperplanes.
We reduce the problem to the rectangle stabbing problem studied by Gaur et al. Their 2-approximation algorithm uses LP rounding. We present an alternative LP-rounding procedure which also works for the rectangle stabbing problem. We show that the integrality ratio of the LP is exactly 2.
Joint work with Adrian Dumitrescu, Howard Karloff, and Peng-Jun Wan.