Given a set S of n points in lRd, we show, for fixed d, how to construct in 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(logn) depth and in which every region is convex and "fat" (that is, has a bounded aspect ratio). While previous hierarchical data structures, such as k-d trees, quadtrees, octrees, fair-split trees, and balanced box decompositions can guarantee some of these properties, we know of no previous data structure that combines alI of these properties simultaneously. The BAR tree data structure has numerous applications ranging from solving several geometric searching problems in fixed dimensional space to aiding in the visualization of graphs and three-dimensional worlds.
Similarly, Duncan et al. REF define the balanced aspect-ratio (BAR) trees, where regions are associated with convex polytopes of bounded aspect ratio, so that the height of the decomposition tree is O(log n).
Balanced aspect ratio trees: combining the advantages of k-d trees and octrees
SODA '99
Mathematics Computer Science