Efficient algorithms for maximum regression depth

M.J. Kreveld, van, J.S.B. Mitchell, P.J. Rousseeuw, M. Sharir, J. Snoeyink, B. Speckmann

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)


We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n d ) time and O(n d-1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog¿2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog¿n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results. A preliminary version of this paper appeared in the proceedings of the 15th Annual ACM Symposium on Computational Geometry (1999)
Original languageEnglish
Pages (from-to)656-677
JournalDiscrete and Computational Geometry
Issue number4
Publication statusPublished - 2008


Dive into the research topics of 'Efficient algorithms for maximum regression depth'. Together they form a unique fingerprint.

Cite this