Separability of point sets by _k-level linear classification trees

Let R and B be sets of red and blue points in the plane in general position. We study the problem of computing a k-level binary space partition (BSP) tree to classify/separate R and B, such that the tree defines a linear decision at each internal node and each leaf of the tree corresponds to a (convex) cell of the partition that contains only red or only blue points. Specifically, we show that a 2-level tree can be computed, if one exists, in time O(n ²). We show that a minimum-level (3 ≤ k ≤ log n) tree can be computed in time n ^{O(log n)}. In the special case of axis-parallel partitions, we show that 2-level and 3-level trees can be computed in time O(n), while a minimum-level tree can be computed in time O(n ⁵).