P.J.: Separating points by axisparallel lines

Peng-Jun Wan ¢ We study the problem of separating £ points in the plane, no two of which have the same ¤ or ¥-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 NP-complete. We give an approximation algorithm with ratio ¦ for the planar problem, and a ratio § approximation algorithm for the §-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 [5]. Their approximation algorithm uses LP-rounding. Our algorithm presents an alternative LP-rounding procedure which also works for the rectangle stabbing problem. We also discuss some dual problems suggested by the linear programs used to solve the separation problem.