We study the problem of separating points in the plane, no two of which have the same or -coordinate using a min- imum 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.
ShomronJacob/Separating-points-by-axis-parallel-lines
We study the problem of separating points in the plane, no two of which have the same or -coordinate using a min- imum 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.
Python