In-Place Randomized Slope Selection

Data Structures

计算机科学;物理学

Henrik Blunck ; Jan Vahrenhold

Others  :  http://drops.dagstuhl.de/opus/volltexte/2006/839/pdf/06091.VahrenholdJan.Paper.839.pdf
PID  :  6520

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

Slope selection, i.e. selecting the slope with rank k among all (_2¯n) lines induced by a collection P of points, results in a widely used robust estimator for linefitting. In this paper, we demonstrate that it is possible to perform slope selection in expected O(n·log_2 n) time using only constant extra space in addition to the space needed for representing the input.