Optimal linear bipartitions of two-colour sets of points in low-dimensional Euclidean spaces

ABSTRACT: A bipartition (a pair of complementary parts) of a set of elements is said to be linear if there is a point in the line so that the two parts are separately included in the two half-lines the point specifies (when the elements are in the line), if there is a line in the plane so that the two parts are separately included in the two half-planes the line specifies (when the elements are in the plane), and if there is a plane in the three-dimensional space so that the two parts are separately included in the two half-spaces the plane specifies (when the elements are in the three-dimensional space). This study develops a method for finding the whole set of linear bipartitions of any finite set of points in the line, plane, and three-dimensional space. The method acts in a progressive way, so that the problem regarding the two-dimensional case is solved in terms of its one-dimensional projections, and that regarding the three-dimensional case in terms of its two-dimensional projections (which in turn may be solved in terms of their one-dimensional projections). Rules for finding optimal linear bipartitions and separators when the points in the set are of two colours are defined and illustrated.