Efficient algorithms for maximum regression depth

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

4 Citaten (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)
Originele taal-2Engels
Pagina's (van-tot)656-677
TijdschriftDiscrete and Computational Geometry
Nummer van het tijdschrift4
StatusGepubliceerd - 2008


Duik in de onderzoeksthema's van 'Efficient algorithms for maximum regression depth'. Samen vormen ze een unieke vingerafdruk.

Citeer dit