Randomized complexity lower bounds for arrangements and polyhedra
| Author(s) : | D. Grigoriev, |
| Publisher : | N/A |
| Publication Date : | 1999 |
| ISSN : | N/A |
| Abstract : | The complexity lower bound \Omega\Gammand / N) for randomized computation trees is proved for recognizing an arrangement or a polyhedron with N faces. This provides in particular, the randomized lower bound\Omega\Gamma n log n) for the DISTINCTNESS problem and generalizes [11] where the randomized lower bound \Omega\Gamma, |