In-Place Randomized Slope-Selection

Abstract

Slope selection is a well-known algorithmic tool used in the context of computing robust
estimators for fitting a line to a collection $mathcal{P}$ of $n$ points in the plane.  We 
demonstrate that it is possible to perform slope selection in expected $mathcal{O}(n log n)$ 
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 Matouv{s}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.