Computing Least Median of Squares Regression Lines and Guided Topological Sweep
- 1 March 1990
- journal article
- research article
- Published by JSTOR in Journal of the American Statistical Association
- Vol. 85 (409) , 115
- https://doi.org/10.2307/2289532
Abstract
Given a set of data points pi = (xi, yi ) for 1 ≤ i ≤ n, the least median of squares regression line is a line y = ax + b for which the median of the squared residuals is a minimum over all choices of a and b. An algorithm is described that computes such a line in O(n 2) time and O(n) memory space, thus improving previous upper bounds on the problem. This algorithm is an application of a general method built on top of the topological sweep of line arrangements.Keywords
This publication has 0 references indexed in Scilit: