TY - CONF
T1 - Balanced aspect ratio trees
T2 - Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
AU - Duncan, Christian A.
AU - Goodrich, Michael T.
AU - Kobourov, Stephen
N1 - Funding Information:
Given a set S of n points on d, 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(log n) depth 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 all of these properties simultaneously. The BAR tree data structure has numerous applications ranging from geometric searching problems in fixed dimensional space to the visualization of graphs and three-dimensional worlds. 2001 Academic Press 1 This paper is a version of 20 which extends the original work in 19 . 2This research partially supported by ARO under grant DAAH04-96-1-0013 while the author was at the Johns Hopkins University. 3This research partially supported by NSF under Grant CCR-9625289 and ARO under Grant DAAH04-96-1-0013.
PY - 1999
Y1 - 1999
N2 - Given a set S of n points in Rd, 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(log n) 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 all 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.
AB - Given a set S of n points in Rd, 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(log n) 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 all 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.
UR - http://www.scopus.com/inward/record.url?scp=0032777413&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032777413&partnerID=8YFLogxK
M3 - Paper
AN - SCOPUS:0032777413
SP - 300
EP - 309
Y2 - 17 January 1999 through 19 January 1999
ER -