Robust Separation of Multiple Sets.

ABSTRACT

Given K finite disjoint sets {Ak }, k = 1, …, K in Euclidean n-space, a general problem with numerous applications is to find K simple nontrivial functions fk (x) which separate the sets {Ak } in the sense that fk (a) ≤ fi (a) for all a ⊂ Ak and i ≠ k, k = 1, …, K. This can always be done (e.g., with the piecewise linear function obtained by the Voronoi Partition defined for the points in [Formula see text]). However, typically one seeks linear functions fk (x) if possible, in which case we say the sets {Ak } are piecewise linear separable. If the sets are separable in a linear sense, there are generally many such functions that separate, in which case we seek a 'best' (in some sense) separator that is referred as a robust separator. If the sets are not separable in a linear sense, we seek a function which comes as close as possible to separating, according to some criterion.