License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-8390
URL: http://drops.dagstuhl.de/opus/volltexte/2006/839/
Blunck, Henrik ; Vahrenhold, Jan

In-Place Randomized Slope-Selection

pdf-format:
Dokument 1.pdf (203 KB)

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:DSP:2006:839,
  author =	{Henrik Blunck and Jan Vahrenhold},
  title =	{In-Place Randomized Slope-Selection},
  booktitle =	{Data Structures},
  year =	{2006},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  number =	{06091},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/839},
  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

DROPS-Home | Fulltext Search | Imprint Published by LZI