Abstract | ||
---|---|---|
A set of n distinct points in the plane defines ((n)(2)) lines by joining each pair of distinct points. The median slope of these O(n(2)) lines was proposed by Theil as a robust estimator for the slope of the line of best fit for the points. We present a randomized algorithm for selecting the k-th smallest slope of such a set of lines which runs in expected O(n log n) time. An efficient implementation of the algorithm and practical experience with the algorithm are discussed. |
Year | DOI | Venue |
---|---|---|
1992 | 10.1142/S0218195992000020 | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
Slope selection, randomized algorithm, Theil-Sen estimator, line fitting, robust estimation | Journal | 2 |
Issue | ISSN | Citations |
1 | 0218-1959 | 32 |
PageRank | References | Authors |
2.11 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael B. Dillencourt | 1 | 498 | 57.58 |
David M. Mount | 2 | 4222 | 479.94 |
Nathan S. Netanyahu | 3 | 2786 | 287.17 |