1 Search Results for "Blunck, Henrik"

In-Place Randomized Slope-Selection

Authors: Henrik Blunck and Jan Vahrenhold

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

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.

Cite as

Henrik Blunck and Jan Vahrenhold. In-Place Randomized Slope-Selection. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

  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/entities/document/10.4230/DagSemProc.06091.4},
  URN =		{urn:nbn:de:0030-drops-8390},
  doi =		{10.4230/DagSemProc.06091.4},
  annote =	{Keywords: In-Place Algorithms, Slope Selection}
  • Refine by Author
  • 1 Blunck, Henrik
  • 1 Vahrenhold, Jan

  • Refine by Classification

  • Refine by Keyword
  • 1 In-Place Algorithms
  • 1 Slope Selection

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2006

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail