We obtain the lower bounds by extending techniques formerly used with respect to algebraic computation trees. These techniques related the complexity to the number of connected components of the set to be recognized. For RAMs, we obtain the correct result by applying a simple topological transformation to the set before counting components.
Our theorems yield lower bounds, many of them tight, for a variety of problems, such as Element Distinctness, Min Gap, Max Gap and Convex Hull.
Joint work with Zvi Galil.