@article {15576,
	title = {Computationally Efficient Algorithms for High-Dimensional Robust Estimators},
	journal = {CVGIP: Graphical Models and Image Processing},
	volume = {56},
	year = {1994},
	month = {1994/07//},
	pages = {289 - 303},
	abstract = {Given a set of n distinct points in d-dimensional space that are hypothesized to lie on a hyperplane, robust statistical estimators have been recently proposed for the parameters of the model that best fits these points. This paper presents efficient algorithms for computing median-based robust estimators (e.g., the Theil-Sen and repeated median (RM) estimators) in high-dimensional space. We briefly review basic computational geometry techniques that were used to achieve efficient algorithms in the 2-D case. Then generalization of these techniques to higher dimensions is introduced. Geometric observations are followed by a presentation of O(nd - 1 log n) expected time algorithms for the d-dimensional Theil-Sen and RM estimators. Both algorithms are space optimal; i.e., they require O(n) storage, for fixed d. Finally, an extension of the methodology to nonlinear domain(s) is demonstrated.},
	isbn = {1049-9652},
	doi = {10.1006/cgip.1994.1026},
	url = {http://www.sciencedirect.com/science/article/pii/S1049965284710261},
	author = {Mount, Dave and Netanyahu,N. S}
}
