Lower Bound for Randomized Linear Decision Trees Recognising a Union of Hyperplanes in a Generic Position
Dima Grigoriev, Marek Karpiński · 1994
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 \cite{1}, but the proof contained a mistake.