|
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 |