The halfspace depth of a point $p$ relative to a data set $S$ in $d$-dimension is the smallest number of data observations from $S$ in any closed halfspace containing $p$. A point with largest depth was considered as the generalization of the median of $S$ by Tukey. The computation of the halfspace depth of a point is equivalent to the closed hemisphere problem, which was shown to be NP-complete by Johnson and Preparata. We propose primal--dual algorithms that update both an upper bound and a lower bound of the depth and terminate as soon as the two bounds coincide. We report preliminary computational experiments. (Joint work with D. Bremner and K. Fukuda)

Whether two sets are seperable 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 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 motivation from problems in pattern classification. (Joint work with Thomas Burger and Peter Gritzmann)

In this talk I present the dual geometry of cycling in the simplex method. A geometric interpretation of the dual can be used not only to visualize cycles - such as Hoffman's famous ``circle'' - but also to construct cyclic linear programs. In fact, I show how to build a linear program, bounded or unbounded, containing a cycle of arbitrary length. This leads to the derivation of a lower bound of $\Omega(n)$ for the maximal cycle length of a linear program in m variables and n inequality constraints.