An Optimal Randomized Algorithm for Maximum Tukey Depth

Research output: Contribution to conferencePaper

Abstract

We present the first optimal algorithm to compute the maximum Tukey depth (also known as location or halfspace 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 ≥ 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; some other applications of this technique are briefly mentioned.

Original languageEnglish (US)
Pages423-429
Number of pages7
StatePublished - Apr 15 2004
Externally publishedYes
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Other

OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'An Optimal Randomized Algorithm for Maximum Tukey Depth'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M. (2004). An Optimal Randomized Algorithm for Maximum Tukey Depth. 423-429. Paper presented at Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States.