Bilinear Separation of Two Sets in n-Space

The NP-complete problem of determining whether two disjoint point sets in the n-dimensional real space R n can be separated by two planes is cast as a bilinear program, that is minimizing the scalar product of two linear functions on a polyhedral set. The bilinear program, which has a vertex solution, is processed by an iterative linear programming algorithm that terminates in a finite number of steps at a point satisfying a necessary optimality condition or at a global minimum. Encouraging computational experience on a number of test problems is reported. 1 Introduction The problem we wish to consider is the following: Given two disjoint points sets A and B in the n-dimensional real space R n , can they be (strictly) separated by two planes? This is a fundamental NP-complete problem [19, 8] that is depicted in Figure 1 for the 2-dimensional real space R 2 . The configurations (a) and (b) of Figure 1 are equivalent as can easily be seen if the roles of A and B are interchanged...