A cost optimal parallel algorithm for balanced decomposition trees

If an edge is removed from a binary tree, the tree is partitioned into two subtrees. If we repeat the partition for each of subtrees recursively, the tree is partitioned into single nodes. A decomposition tree is a binary tree which shows the above partition process. In addition, the decomposition tree is called balanced if all recursive partitions are balanced. In the paper, the authors propose a cost optimal parallel algorithm for computing balanced decomposition trees on the CREW PRAM model. The algorithm runs in O(log n) time using O(n/log n) processors. Using the algorithm, we also propose a cost optimal algorithm for a geometric problem.