Exponential Lower Bound for Static Semi-algebraic Proofs.

Dima Grigoriev Edward A. Hirsch Dmitrii V. Pasechnik

Published in: ICALP (2002)

Keyphrases

lower bound
semi algebraic
upper bound
spatial databases
branch and bound algorithm
arbitrary dimension
objective function
optimal solution
worst case
sufficiently accurate
nearest neighbor
databases
computationally efficient
range queries
database
lower and upper bounds
multiresolution
high dimensional