Slope selection is a well-known algorithmic tool used in the context of computing robust estimators for fitting a line to a collection P of n points in the plane. We demonstrate that it is possible to perform slope selection in expected O(nlogn) time using only constant extra space in addition to the space needed for representing the input. Our solution is based upon a space-efficient variant of Matoušek’s randomized interpolation search, and we believe that the techniques developed in this paper will prove helpful in the design of space-efficient randomized algorithms using samples. To underline this, we also sketch how to compute the repeated median line estimator in an in-place setting.
Algorithms and Complexity: 6th Italian Conference, Ciac 2006, Rome, Italy, May 29-31, 2006. Proceedings, 2006, p. 30-41
6th Italian Conference on Algorithms and Complexity. CIAC 2006