Robust separation of multiple sets

✍ Scribed by Lana E Yeganova; James E Falk; Yelena V Dandurova

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 350 KB
• Volume: 47
• Category: Article
• ISSN: 0362-546X
• DOI: 10.1016/s0362-546x(01)00315-7

✦ Synopsis

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