An Optimal Randomized Algorithm for Maximum Tukey Depth

Research output: Contribution to conferencePaperpeer-review

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 - 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
Country/TerritoryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

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

Cite this