A near linear algorithm for testing linear separability in two dimensions

International audienceWe present a near linear algorithm for determining the linear separability of two sets of points in a two-dimensional space. That algorithm does not only detects the linear separability but also computes separation information. When the sets are linearly separable, the algorithm provides a description of a separation hyperplane. For non linearly separable cases, the algorithm indicates a negative answer and provides a hyperplane of partial separation that could be useful in the building of some classification systems