A RANDOMIZED ALGORITHM FOR SLOPE SELECTION

被引：37

作者：

Dillencourt, Michael B. ^{[1
]}

Mount, David M. ^{[2
,3
]}

Netanyahu, Nathan S. ^{[4
]}

机构：

[1] Univ Calif Irvine, Dept Informat & Comp Sci, Irvine, CA 92717 USA

[2] Univ Maryland, Dept Comp Sci, College Pk, MD 20742 USA

[3] Univ Maryland, Inst Adv Comp Studies, College Pk, MD 20742 USA

[4] Univ Maryland, Ctr Automat Res, Comp Vis Lab, College Pk, MD 20742 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1992年 / 2卷 / 01期

基金：

美国国家科学基金会;

关键词：

Slope selection; randomized algorithm; Theil-Sen estimator; line fitting; robust estimation;

D O I：

10.1142/S0218195992000020

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：1 / 27

页数：27

共 31 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2] FAST PROBABILISTIC ALGORITHMS FOR HAMILTONIAN CIRCUITS AND MATCHINGS [J].

ANGLUIN, D ;

VALIANT, LG .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1979, 18 (02) :155-193

[3]

[Anonymous], 1950, P R NETHERLANDS ACAD

[4]

[Anonymous], 2003, ROBUST REGRESSION OU

[5]

BENTLEY JL, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P91

[6] AN OPTIMAL-TIME ALGORITHM FOR SLOPE SELECTION [J].

COLE, R ;

SALOWE, JS ;

STEIGER, WL ;

SZEMEREDI, E .

SIAM JOURNAL ON COMPUTING, 1989, 18 (04) :792-810

[7]

Dahlquist G., 1974, NUMERICAL METHODS

[8]

Donoho D. L., 1983, FESTSCHRIFT L LEHMAN, P157

[9] USE OF HOUGH TRANSFORMATION TO DETECT LINES AND CURVES IN PICTURES [J].

DUDA, RO ;

HART, PE .

COMMUNICATIONS OF THE ACM, 1972, 15 (01) :11-&

[10] COMPUTING LEAST MEDIAN OF SQUARES REGRESSION LINES AND GUIDED TOPOLOGICAL SWEEP [J].

EDELSBRUNNER, H ;

SOUVAINE, DL .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1990, 85 (409) :115-119

← 1 2 3 4 →