Before revision:  Finally, we give an \Omega(n\log n) lower bound on the problem , showing that our quadtree algorithms are almost tight.
After revision:  Finally, we give an \Omega(n\log n) lower bound , showing that our quadtree algorithms are almost tight.