Parallel construction of quadtrees and quality triangulations.
M. Bern,
D. Eppstein, and
S.-H. Teng.
3rd Worksh. Algorithms and Data
Structures, Montreal, 1993,
doi:10.1007/3-540-57155-8_247.
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,
doi:10.1142/S0218195999000303.
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.