Efficient algorithms for maximum regression depth
Marc J. van Kreveld, Joseph S. B. Mitchell, Peter J. Rousseeuw, Micha Sharir, Jack Scott Snoeyink, Bettina Speckmann · 1999
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(nd) time and space algorithm computes directed depth of all points in d dimensions.Properties of undirected depth lead to an O(n log2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions.We also give approximation algorithms for hyperplane arrangements and degenerate line arrangements.