The Art Gallery Guardian

Pack a histogram


Consider we have a histogram of nn values and nn distinct colors. The iith bar is a rectangle of size 1×vi1\times v_i, where viv_i is the value and has color ii. The total area of all the bars are nn. We are interested in make a few cuts to pack it into nn squares each one of area 11, such that each square is consist of at most 22 different colors.

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

Problem1

Input: (v1,1),,(vn,n)(v_1,1),\ldots,(v_n,n).

Output: S={s1,,sn}S=\{s_1,\ldots,s_n\}, such that si={(x2i1,c2i1),(x2i,c2i)}s_i = \{(x_{2i-1},c_{2i-1}),(x_{2i},c_{2i})\}, x2i+x2i1=1x_{2i}+x_{2i-1}=1 and for all 1in1 \leq i\leq n, sS(x,i)sx=vi.\displaystyle \sum_{s\in S} \sum_{(x,i)\in s} 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. (vi,i)(v_i,i) is in the large bin if vi>1v_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)(x,i) and (y,j)(y,j), where x1<yx\leq 1< y. Now we create a set {(x,i),(1x,j)}\{(x,i),(1-x,j)\}, and put (y(1x),j)(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 .
Tags: classical, algorithm.