TY - JOUR
T1 - Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses
JF - Computational Geometry
Y1 - 2001
A1 - Mount, Dave
A1 - Netanyahu,Nathan S.
KW - Aligned ellipse fitting
KW - Arrangements
KW - Circular arc fitting
KW - computational geometry
KW - randomized algorithms
KW - Range searching
KW - RM estimator
KW - robust estimation
KW - Theil–Sen estimator
AB - 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–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.
VL - 19
SN - 0925-7721
UR - http://www.sciencedirect.com/science/article/pii/S0925772101000098
CP - 1
M3 - 10.1016/S0925-7721(01)00009-8
ER -