On constructing binary space partitioning trees
Ravinder Krishnaswamy, Ghasem S. Alijani, Shyh-Chang Su · 1990
Binary Space Partitioning Trees have several applications in computer graphics. We prove that there exist n-polygon problem instances with an O(n2) lower bound on tree size. We also show that a greedy algorithm may result in constructing a tree with O(n2) nodes, while there exist a tree for the same n-polygon instance with only O(n) nodes. Finally, we formulate six different heuristics and test their performance.