Algorithms Seminar 2003

Whether two sets are separable by hyperplanes is invariant under affine transformations, while distance is not. The near universal reduction of separation problems in practice to distance computations is on the surface thus a bit of a mystery. In this talk I will argue that the connection between distance and separation is necessary and natural as soon as one asks for the ``best'' separating hyperplane. On the other hand, it is often much more convenient to work with distance metrics different from the standard Euclidean one. It turns out that for polytopal metrics a strong duality relationship between distance and separation allows the straightforward computation of optimal separating hyperplanes by solving a primal-dual pair of linear programs. An especially interesting feature of this framework is that it works for input given explicitly as sets of points (where an LP solution is relatively well known, even for the Euclidean metric), but also for input given implicitly as intersections of halfspaces and Minkowski sums of line segments. I will round out the talk by discussing some possible approaches to the case when two sets are not separable by a hyperplane, and some connections with problems in pattern classification.

(Work with Thomas Burger and Peter Gritzmann)