Parallel construction of quadtrees and quality triangulations.
M. Bern,
D. Eppstein, and
S.-H. Teng.
3rd Worksh. Algorithms and Data
Structures, Montreal, 1993.
Springer, Lecture Notes in
Comp. Sci. 709, 1993, pp. 188–199.
Tech. Rep. 614, MIT Lab. for Comp. Sci., 1994.
Int. J. Comp. Geom. & Appl.
9 (6): 517–532, 1999.
A parallelization of the quadtree constructions in "Provably good mesh generation", in an integer model of computation, based on a technique of sorting the input points using values formed by shuffling the binary representations of the coordinates. A side-effect is an efficient construction for the "fair split tree" hierarchical clustering method used by Callahan and Kosaraju for various nearest neighbor problems.