Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees

Given a set S of n points on R-d, we show, for fixed Li, how to construct i n O(n log n) time a data structure we call the balanced aspect ratio (BAR) tree. A BAR tree is a binary space partition tree on S that has O(log n) de pth in which every region is convex and "fat" (that is, has a bounded aspec t ratio). While previous hierarchical data structures such as k-d trees, qu adtrees, octrees, fair-split trees, and balanced box decompositions can gua rantee some of these properties, we know of no previous data structure that combines all of these properties simultaneously. The BAR tree data structu re has numerous applications ranging from geometric searching problems in f ixed dimensional space to the visualization of graphs and three-dimensional worlds, (C) 2001 Academic Press.