Optimal Partition Trees |
| |
Authors: | Timothy M. Chan |
| |
Affiliation: | (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 等数据库收录! |
|
|