Pack a histogram

Consider we have a histogram of $n$ values and $n$ distinct colors. The $i$ th bar is a rectangle of size $1 \times v_{i}$ , where $v_{i}$ is the value and has color $i$ . The total area of all the bars are $n$ . We are interested in make a few cuts to pack it into $n$ squares each one of area $1$ , such that each square is consist of at most $2$ different colors.

Formally, we are seeking an algorithm for the following problem:

Problem1

Input: $(v_{1}, 1), \dots, (v_{n}, n)$ .

Output: $S = {s_{1}, \dots, s_{n}}$ , such that $s_{i} = {(x_{2 i - 1}, c_{2 i - 1}), (x_{2 i}, c_{2 i})}$ , $x_{2 i} + x_{2 i - 1} = 1$ and for all $1 \leq i \leq n$ , $s \in S \sum (x, i) \in s \sum x = v_{i} .$

Here is an algorithm that make sure this can be done in linear time. The idea is to separate the numbers into two bins. $(v_{i}, i)$ is in the large bin if $v_{i} > 1$ , and it is in the small bin otherwise. The idea is always pick two elements, one in large bin one in small bin, say $(x, i)$ and $(y, j)$ , where $x \leq 1 < y$ . Now we create a set ${(x, i), (1 - x, j)}$ , and put $(y - (1 - x), j)$ back into the bins.

If we can always prove that there is an element in the small bin during the execution of the algorithm, then we find an linear time algorithm for this problem. This is clear by simple induction.

This problem come up in order to implement the alias method. I recommend a good read on this topic Darts, Dice, and Coins: Sampling from a Discrete Distribution by Keith Schwarz.

Posted by Chao Xu on 2014-10-12.

Tags: classical, algorithm.