# ICS 269, Winter 2004: Theory Seminar

## 20 Feb 2004:

An Optimal Randomized Algorithm for Maximum Tukey Depth

Kevin Wortman

We present the first algorithm to compute the maximum Tukey
depth for a non-degenerate point set in the plane. The algorithm is
randomized and requires *O*(*n* log *n*)
expected time for *n* data points.
In a higher fixed dimension *d*, greater than or equal to 3,
the expected time bound is *O*(*n*^{d-1}),
which is probably optimal as well. The result is obtained using an
interesting variant of the author's randomized optimization
technique, capable of solving "implicit" linear-programming-type problems.

From: Paper by the same name, by Timothy Chan, Proc. 15th ACM-SIAM Symp.
Discrete Algorithms (SODA), Jan 2004, pp. 423-429.