Dm. Mount et Ns. Netanyahu, Efficient randomized algorithms for robust estimation of circular arcs andaligned ellipses, COMP GEOM, 19(1), 2001, pp. 1-33
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 s
tatistical estimation and has significant industrial applications. Recently
there has been a great deal of interest in robust estimators, because of t
heir lack of sensitivity to outlying data points. The basic measure of the
robustness of an estimator is its breakdown point, that is, the fraction (u
p to 50%) of outlying data points that can corrupt the estimator. In this p
aper we introduce nonlinear Theil-Sen and repeated median (RM) variants for
estimating the center and radius of a circular are, and for estimating the
center and horizontal and Vertical radii of an axis-aligned ellipse. The c
ircular are estimators have breakdown points of approximate to 21% and 50%.
respectively, and the ellipse estimators have breakdown points of approxim
ate to 16% and 50%, respectively. We present randomized algorithms for thes
e estimators, whose expected running times are O(n(2) log n) for the circul
ar case and O(n(3) log n) for the elliptical case. All algorithms use O(n)
space in the worst case, (C) 2001 Elsevier Science B.V. All rights reserved
.