Abstract
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 language | English |
---|---|
Pages (from-to) | 656-677 |
Journal | Discrete and Computational Geometry |
Volume | 39 |
Issue number | 4 |
DOIs | |
Publication status | Published - 2008 |