1 An Optimal Balanced Partitioning of a Set of 1D Intervals

Given a set of 1D intervals and a desired partition number, this paper studies on how to make an optimal partitioning of these intervals, such that the number of intervals between the largest partition and smallest partition is minimal among all possible parti-tioning schemes. Though seemingly easy at the first glance, this problem has its difficul-ty due to the fact that an interval ``striding' ' multiple partitions should be counted mul-tiple times. Previously we have given an approximated solution to this problem by em-ploying a simulated annealing approach [Yang & Chiueh, 2006], which could give satis-factory results in most cases; however, there is no theoretical guarantee on its optimality. In this paper, we propose a method that could both optimally and deterministically parti-tion a given set of 1D intervals into a given number of partitions. This problem originates from dealing with the partition of a large volume data, where a more balanced partition-ing could facilitate efficient out-of-core volume visualization faced in the computer graphics world. We will show that some types of load balancing problem could also be formulated as a balanced interval partitioning problem. As a result, seeking better solu-tions to this problem has become an important issue