2026-07-20T09:02:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:839 2024-03-06T11:06:44Z ddc:004 open_access

In-Place Randomized Slope-Selection Blunck, Henrik Vahrenhold, Jan In-Place Algorithms Slope Selection 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henrik Blunck and Jan Vahrenhold 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06091.4 urn:nbn:de:0030-drops-8390 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.4 eng https://creativecommons.org/licenses/by/4.0/legalcode