Blunck, Henrik ;
Vahrenhold, Jan
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.
BibTeX - Entry
@InProceedings{blunck_et_al:DagSemProc.06091.4,
author = {Blunck, Henrik and Vahrenhold, Jan},
title = {{In-Place Randomized Slope-Selection}},
booktitle = {Data Structures},
pages = {1--4},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2006},
volume = {6091},
editor = {Lars Arge and Robert Sedgewick and Dorothea Wagner},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2006/839},
URN = {urn:nbn:de:0030-drops-8390},
doi = {10.4230/DagSemProc.06091.4},
annote = {Keywords: In-Place Algorithms, Slope Selection}
}
|
Keywords: |
|
In-Place Algorithms, Slope Selection |
|
Seminar: |
|
06091 - Data Structures
|
|
Issue date: |
|
2006 |
|
Date of publication: |
|
30.11.2006 |
30.11.2006
