 Finally, we give an \Omega(n\log n) lower bound on the problem , showing that our quadtree algorithms are almost tight.
<clarity>  Finally, we give an \Omega(n\log n) lower bound on the problem , showing that our quadtree algorithms are almost tight.
 Finally, we give an \Omega(n\log n) lower bound , showing that our quadtree algorithms are almost tight.