TY - JOUR
T1 - Balanced Aspect Ratio Trees
T2 - Combining the Advantages of k-d Trees and Octrees
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 - 2001/1
Y1 - 2001/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0001470860&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0001470860&partnerID=8YFLogxK
U2 - 10.1006/jagm.2000.1135
DO - 10.1006/jagm.2000.1135
M3 - Article
AN - SCOPUS:0001470860
SN - 0196-6774
VL - 38
SP - 303
EP - 333
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -