@article {15572,
	title = {A practical approximation algorithm for the LMS line estimator},
	journal = {Computational Statistics \& Data Analysis},
	volume = {51},
	year = {2007},
	month = {2007/02/01/},
	pages = {2461 - 2486},
	abstract = {The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of n points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0 \&lt; q ⩽ 1 . This problem is equivalent to finding the strip defined by two parallel lines of minimum vertical separation that encloses at least half of the points.The best known exact algorithm for this problem runs in O ( n 2 ) time. We consider two types of approximations, a residual approximation, which approximates the vertical height of the strip to within a given error bound ε r ⩾ 0 , and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound ε q ⩾ 0 . We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and ε q \&gt; 0 runs in O ( n log n ) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm{\textquoteright}s expected running time is O ( n log 2 n ) . We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm.
},
	keywords = {Approximation algorithms, least median-of-squares regression, line arrangements, line fitting, randomized algorithms, robust estimation},
	isbn = {0167-9473},
	doi = {10.1016/j.csda.2006.08.033},
	url = {http://www.sciencedirect.com/science/article/pii/S0167947306002921},
	author = {Mount, Dave and Netanyahu,Nathan S. and Romanik,Kathleen and Silverman,Ruth and Wu,Angela Y.}
}
@article {15567,
	title = {Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses},
	journal = {Computational Geometry},
	volume = {19},
	year = {2001},
	month = {2001/06//},
	pages = {1 - 33},
	abstract = {Fitting two-dimensional conic sections (e.g., circular and elliptical arcs) to a finite collection of points in the plane is an important problem in statistical estimation and has significant industrial applications. Recently there has been a great deal of interest in robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50\%) of outlying data points that can corrupt the estimator. In this paper we introduce nonlinear Theil{\textendash}Sen and repeated median (RM) variants for estimating the center and radius of a circular arc, and for estimating the center and horizontal and vertical radii of an axis-aligned ellipse. The circular arc estimators have breakdown points of ≈~21\% and 50\%, respectively, and the ellipse estimators have breakdown points of ≈ 16\% and 50\%, respectively. We present randomized algorithms for these estimators, whose expected running times are O(n2logn) for the circular case and O(n3logn) for the elliptical case. All algorithms use O(n) space in the worst case.},
	keywords = {Aligned ellipse fitting, Arrangements, Circular arc fitting, computational geometry, randomized algorithms, Range searching, RM estimator, robust estimation, Theil{\textendash}Sen estimator},
	isbn = {0925-7721},
	doi = {10.1016/S0925-7721(01)00009-8},
	url = {http://www.sciencedirect.com/science/article/pii/S0925772101000098},
	author = {Mount, Dave and Netanyahu,Nathan S.}
}
@conference {15625,
	title = {A practical approximation algorithm for the LMS line estimator},
	booktitle = {Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms},
	series = {SODA {\textquoteright}97},
	year = {1997},
	month = {1997///},
	pages = {473 - 482},
	publisher = {Society for Industrial and Applied Mathematics},
	organization = {Society for Industrial and Applied Mathematics},
	address = {Philadelphia, PA, USA},
	keywords = {Approximation algorithms, least median-of-squares regression, line arrangements, line fitting, randomized algorithms, robust estimation},
	isbn = {0-89871-390-0},
	url = {http://dl.acm.org/citation.cfm?id=314161.314349},
	author = {Mount, Dave and Netanyahu,Nathan S. and Romanik,Kathleen and Silverman,Ruth and Wu,Angela Y.}
}
