Optimal Partition Trees |
| |
| Authors: | Timothy M Chan |
| |
| Institution: | (1) Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada |
| |
| Abstract: | We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Matoušek
(Discrete Comput. Geom. 10:157–182, 1993) gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n
1−1/d
) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n
1+ε
) preprocessing time for any fixed ε>0. An earlier method by Matoušek (Discrete Comput. Geom. 8:315–334, 1992) requires O(nlogn) preprocessing time but O(n
1−1/d
log
O(1)
n) query time. We give a new method that achieves simultaneously O(nlogn) preprocessing time, O(n) space, and O(n
1−1/d
) query time with high probability. Our method has several advantages:
| •
|
It is conceptually simpler than Matoušek’s O(n
1−1/d
)-time method. Our partition trees satisfy many ideal properties (e.g., constant degree, optimal crossing number at almost
all layers, and disjointness of the children’s cells at each node). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
|
