### 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(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; some other applications of this technique are briefly mentioned.

Original language | English (US) |
---|---|

Pages | 423-429 |

Number of pages | 7 |

State | Published - Apr 15 2004 |

Externally published | Yes |

Event | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: Jan 11 2004 → Jan 13 2004 |

### Other

Other | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | New Orleans, LA. |

Period | 1/11/04 → 1/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.