Med tanke på en uppsättning S av n punkter i lRd, visar vi, för fast d, hur man konstruerar i O(n log n) tid en datastruktur som vi kallar Balanserad Aspect Ratio (BAR) träd. Ett barträd är ett binärt utrymme partition träd på S som har O (logn) djup och där varje region är konvex och "fett" (dvs. har en begränsad proportion). Medan tidigare hierarkiska datastrukturer, såsom k-d träd, quadtrees, oktrees, fair-split träd, och balanserade box nedbrytningar kan garantera några av dessa egenskaper, vi känner till ingen tidigare datastruktur som kombinerar alI av dessa egenskaper samtidigt. Den BAR träd datastruktur har många tillämpningar som sträcker sig från att lösa flera geometriska sökproblem i fast dimensionsutrymme till att hjälpa till att visualisera grafer och tredimensionella världar.
På samma sätt, Duncan et al. I REF definieras balanserade aspect-ratio (BAR) träd, där regioner är associerade med konvexa polytoper med avgränsad proportion, så att sönderfallsträdets höjd är O(log n).
Balanced aspect ratio trees: combining the advantages of k-d trees and octrees
{'venue': "SODA '99", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}