|
University of Bonn -> Department of Computer Science -> Chair V | ||
CS-APX-Reports 1994 | Copyright 1994 University of Bonn, Department of Computer Science, 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
Deutsch |
University of Bonn -> Department of Computer Science -> Chair V |