Robust Separation of Multiple Sets

Given K finite disjoint sets {A^k }, k = 1, …, K in Euclidean n-space, a general problem with numerous applications is to find K simple nontrivial functions f_k (x) which separate the sets {A^k } in the sense that f_k (a) ≤ f_i (a) for all a ⊂ A^k 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 f_k (x) if possible, in which case we say the sets {A^k } 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.