**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.

(BibTeX – CiteSeer – Citations – ACM DL)

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.