Linear and Nonlinear Separation of Patterns by Linear Programming

A pattern separation problem is basically a problem of obtaining a criterion for distinguishing between the elements of two disjoint sets of patterns. The patterns are usually represented by points in a Euclidean space. One way to achieve separation is to construct a plane or a nonlinear surface such that one set of patterns lies on one side of the plane or the surface, and the other set of patterns on the other side. Recently, it has been shown that linear and ellipsoidal separation may be achieved by nonlinear programming. In this work it is shown that both linear and nonlinear separation may be achieved by linear programming.