SEPARATING POINTS BY AXIS-PARALLEL LINES has applications to fault-tolerant multi- modal sensor fusion in the context of embedded sensor networks. In the following, by line we mean axis-parallel line.
This problem is so-called NP-hard, and therefore polynomial-time algorithms are very unlikely to exist. We have to settle for approximate solutions – that is our algorithms are not guaranteed to return the optimum solution. Such algorithms are called heuristics, and the project asks you to implement two such algorithms.
SEPARATING POINTS BY AXIS-PARALLEL LINES was studied by the instructor, and http://www.cs.iit.edu/~calinesc/separating.pdf describes a polynomial-time algorithms guar- anteed to return a solution at most twice the optimum solution. This is a complicated algorithm and simpler heuristics might do better in practice.
The first heuristics you are asked to implement is the following local-optimization procedure. Start with an arbitrary feasible solution. Try all combinations of two lines from the current feasible solution, and another line. If the removal of the two lines followed by the addition of the other line results in another feasible solution, then proceed and change the current feasible solution. Repeat trying all combinations, until no combination leads to another feasible solution. Such procedure is used by the meta-heuristic method Simulated Annealing.