Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1994 Copyright 1994 Universität Bonn, Institut für Informatik, Abt. V
8918

Lower Bound for Randomized Linear Decision Trees Recognising a Union of Hyperplanes in a Generic Position
Dima Grigoriev, Marek Karpinski
[Download PostScript] [Download PDF]

Let $L$ be a union of hyperplanes with $s$ vertices. We prove that the runtime of a probabilistic linear search tree recognizing membership to $L$ is at least $\Omega\,(\log s)$, provided that $L$ satisfies a certain condition which could be treated as a generic position. A more general statement, namely without the condition, was claimed by F. Meyer auf der Heide [1], but the proof contained a mistake.

Last Change: 11/05/14 at 09:53:04
 English
Universität Bonn -> Institut für Informatik -> Abteilung V