The Art Gallery Guardian

More algorithms on perfectly balanced photo gallery


Recently there was an article by Johannes Treitz submitted to Hacker News about how to display a set of pictures as nicely as possible. The article doesn’t have a formal description of the problem, so here is my take on what it mean by perfectly balanced.

Problem1

Given a sequence of rectangles where the th rectangle has width and height . Also given are width and target height . Partition the sequence to consecutive subsequences, such that we scale the rectangles keeping the aspect ratio, and each subsequence of rectangles fills the entire width , and is close to the target height .

The problem is not so well defined. To make sure the heights are close, do we minimize the sum of all differences? Minimize the maximum difference? Or maybe, we just want to minimize the difference between consecutive rows, such that the first row has height close to .

Nevertheless, in real applications, the exact definition doesn’t matter that much. Treitz reduce the problem to the linear partition problem.

Problem2

Let be a sequence of positive reals. We want to partition it into consecutive subsequences, such that the maximum sum over each subsequence is minimized. Formally, find positions , such that is minimized.

is the aspect ratio. This article will explore the techniques to solve the problem in time. It is only a high level overview, and leaves the details unfilled.

1 Minimize total difference

Let’s first consider a simpler problem for demonstration.

Problem3

Let be a sequence of positive reals. We want to partition it into consecutive subsequences, such that the total difference between the sum of each consecutive sequence and the average sum of the whole sequence is minimized. Formally, let . Find positions , such that is minimized.

We will solve this problem with a reduction to a problem on a DAG, and then apply dynamic programming. Since we can always turn a problem that ask us to find the cost to a problem that ask us to find a construction that achieve the cost(with the same time/space bound). We will only concern with the cost version of the problem as it’s much clearer. (One can implement some arrows in Haskell to make DP for construction as easy as DP for cost, sounds like a nice project. )

Build a directed graph , where , if and only if . (We can make it instead, depend on if we consider a empty sequence a valid sequence.)

We have a weight function that assign weights to arc . Define .

If we find a -edge path of minimum weight from to , then this implies a solution to Problem 3.

2 Solve the minimum weight -edge path problem

Define to be the -edge path from to with minimum weight. We want to find .

If we set if , then we have a better representation.

There are entries in the DP table for , and requires time to compute. This means the algorithm will take time.

3 Improve the time complexity

There is a standard technique on totally monotone matrices that can reduce the complexity of the problem to .

Definition4

A weight function is Monge if for every , we have

Theorem5

is Monge.

Proof

Let To prove the , see that are positive, one can consider either is negative or positive, and notice either way the inequality holds true.

Remark

We can replace with for . When , we minimizes the variance(and standard deviation).

Definition6

A matrix is totally monotone if for every and , .

totally monotone
Image Credit: Vanessa Li.

Remark

There are isomorphic definition of Monge and totally monotone, depend on if the person want to find row or column minima.

Define a matrix , such that , the original recurrence become In other words, is the th column’s minima of .

Theorem7

If is Monge, then is a totally monotone matrix.

Using the SMAWK algorithm, all column minimas can be found in . Finding takes only time on average!

Here is the very simple code to show how this can be done easily if we have a Haskell implementation of the SMAWK algorithm. The indexing is a bit different from the description in the article.

import Data.Array
import SMAWK

minCostkEdgePath k n w = d!(k-1,n)
  where
    d = array ((0,0),(k-1,n)) [ ((i,j), f i j) | i<-[0..k-1],j<-[0..n]]
    f 0 i = w 0 i
    f k i = m k (p!(k,i)) i
    p = array ((1,0),(k,n)) [((z,i),t) |z<-[1..k],(i,t)<-zip [0..n] (columnMinima (m z) (n+1) (n+1))]
    m k j i = (+) (d!(k-1,j)) (w j i)

minCostMuPartition k xs = minCostkEdgePath k n w
    where 
        w i j 
         | i <= j    = abs $! s!j - s!i - avg
         | otherwise = 2*m
        s   = listArray (0, n-1) $ scanl (+) 0 xs
        n   = length xs
        m   = sum xs
        avg = m/fromIntegral k

4 Solve the linear partition problem

Now, returning to the original problem. Again, we can reduce the problem to a problem on a directed graph. This time, . The weight of a path is the maximum weight of the edges in the path. A -edge path with minimum weight implies the solution to the original problem.

where .

Just like Problem 3, this describes a time algorithm. Compare and with the previous problem to see there isn’t much difference.

5 Improve the time complexity, again

Can we define an alternative to the Monge property? Yes, we can extend this to algebraic Monge property. Just replace with some associative operation , with a total order that is ordered with respect to , i.e. .

So it seems, using the algorithm above with little modification, we can solve the problem in time because we can just replace by .

However, algebraic Monge property in general doesn’t imply totally monotone matrix.

Consider the simple matrix, and our operation is .

, but the matrix is not totally monotone. but .

If instead the operation is strictly compatible, i.e.  if , then we can always produce a totally monotone matrix. This is not the case with .

Some readers who are familiar with space might point out for any sequence of reals and , there exist a , such that . So if we don’t need to be exact, pick a large enough as an exponential is good enough. This opens up a can of numerical analysis.

A more restrictive but good enough variant of the Monge property hold.

Definition8

has the strict bottleneck Monge property if either of the following is true for :

  1. .
  2. and .

Our in consideration has strict bottleneck Monge property. Because all the numbers are positive, , . A simple case check on the relation between and will give the desired proof. Why this property? You can check by a case by case proof that this property implies total monotonicity.

Theorem9

If has the strict bottleneck Monge property, then is a totally monotone matrix.

There seems to be a direct proof by analyze 12 different cases, but I got too bored after the second case. One can read [1] for the proof. It doesn’t contain the exact theorem, but a result that implies this one. The proof is quite involved. Their idea is to construct a new matrix with a new operation over sorted sequences of numbers instead of just numbers. Prove this matrix is strictly compatible and has the algebraic Monge property, and show this can always be done if the original matrix has the strict bottleneck Monge property.

The final punchline.

Theorem10

Change the last (+) in minCostkEdgePath to max, and change how w is computed in minCostMuPartition solves Problem 2.

6 Rethink the original problem

We have developed a algorithm for Problem 2. As we can see from the practical application, this is a algorithm because the is of the order .

For a few hundred photos, we can afford to run it in real time. This will reach a limit once there are thousand of photos.

Can we do better? Yes, by considering a different kind of reduction(thank god we didn’t formally define what close means). Instead of compute and try to fit rows, why not just make sure each row’s width is almost the width we want and scale accordingly? We want each rows to approximately have width , we don’t really care how many rows there are.

Problem11

Let be a sequence of positive reals, and a number . We want to partition it into consecutive subsequences, such that the maximum difference between the sum of each consecutive sequence and the is minimized. Formally, find a and a sequence of numbers , such that is minimized.

This is the exact same problem described on section 5 of [1]. It can be solve in time.

7 Update

We did some more investigation into this problem.

References

[1]
W. Bein, P. Brucker, L.L. Larmore, J.K. Park, The algebraic monge property and path problems, Discrete Applied Mathematics. 145 (2005) 455–464 10.1016/j.dam.2004.06.001.
Posted by Chao Xu on .
Tags: Algorithm.