Efficient algorithms for maximum regression depth

Marc van Kreveld; Joseph S.B. Mitchell; Peter Rousseeuw; Micha Sharir; Jack Snoeyink; Bettina Speckmann

doi:10.1145/304893.304901

Efficient algorithms for maximum regression depth

Marc van Kreveld
, Joseph S.B. Mitchell
, Peter Rousseeuw
, Micha Sharir
, Jack Snoeyink
, Bettina Speckmann

Applied Mathematics and Statistics

Utrecht University

Research output: Contribution to conference › Paper › peer-review

12 Scopus citations

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 space algorithm computes directed depth of all points in d dimensions. Properties of undirected depth lead to an O(n log² 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.

Original language	English
Pages	31-40
Number of pages	10
DOIs	https://doi.org/10.1145/304893.304901
State	Published - 1999
Event	Proceedings of the 1999 15th Annual Symposium on Computational Geometry - Miami Beach, FL, USA Duration: Jun 13 1999 → Jun 16 1999

Conference

Conference	Proceedings of the 1999 15th Annual Symposium on Computational Geometry
City	Miami Beach, FL, USA
Period	06/13/99 → 06/16/99

Access to Document

10.1145/304893.304901

Cite this

@conference{8d932f87d0fd4e64ab33fc6a2abe55f8,

title = "Efficient algorithms for maximum regression depth",

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(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.",

author = "\{van Kreveld\}, Marc and Mitchell, \{Joseph S.B.\} and Peter Rousseeuw and Micha Sharir and Jack Snoeyink and Bettina Speckmann",

year = "1999",

doi = "10.1145/304893.304901",

language = "English",

pages = "31--40",

note = "Proceedings of the 1999 15th Annual Symposium on Computational Geometry ; Conference date: 13-06-1999 Through 16-06-1999",

}

TY - CONF

T1 - Efficient algorithms for maximum regression depth

AU - van Kreveld, Marc

AU - Mitchell, Joseph S.B.

AU - Rousseeuw, Peter

AU - Sharir, Micha

AU - Snoeyink, Jack

AU - Speckmann, Bettina

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0032683174

U2 - 10.1145/304893.304901

DO - 10.1145/304893.304901

M3 - Paper

AN - SCOPUS:0032683174

SP - 31

EP - 40

T2 - Proceedings of the 1999 15th Annual Symposium on Computational Geometry

Y2 - 13 June 1999 through 16 June 1999

ER -

Efficient algorithms for maximum regression depth

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this