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(nd-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.