Advertisement
Published in:
2006 | OriginalPaper | Chapter
In-Place Randomized Slope Selection
Authors : Henrik Blunck, Jan Vahrenhold
Published in: Algorithms and Complexity
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 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.