Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1994 Copyright 1994 University of Bonn, Department of Computer Science, Abt. V
85114

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