Optimal partition trees
Timothy M. Chan · 2010
We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Back in SoCG'92, Matousek gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n1-1/d) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n1+ε) preprocessing time for any fixed ε>0. An earlier method by Matousek (SoCG'91) requires O(n log n) preprocessing time but O(n1-1/d logO(1)n) query time. We give a new method that achieves simultaneously O(n log n) preprocessing time, O(n) space, and O(n1-1/d) query time with high probability. Our method has several advantages: