Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I first came across that algorithm as the "Random minimum cut" algorithm. And recently a colleague was trying to pack a big quantity of small textures into one image file. Then it clicked - why not use Karger for this packing problem?

I don't know a good way to map this problem to a graph defined in order to minimize the wasted space between images.

Here I define the minimum cut as "the atlas with less blank filler pixels". So I need to generate a graph that represents a "distance" between images as an edge. Any suggestion on what type of distance to use?

Here is the first idea I had:

Given an image A(w, h) where w is width and h is height, if B(w', h') exists for w = w' or h = h' create an edge between A and B. (The same rule with a certain tolerance could be used, like + or - 1%).

I would be very surprised if I am the first one to think about this. So if anybody knows about anything similar that has been done, please do say so.

share|improve this question
i think, your question was answered here… – c69 Aug 18 '13 at 16:12
I know this problem has been solved in other ways. But for pure curiosity and the potential for awesomeness I wanted to see if a randomized approach would work. Krager's has the neat advantage to give the wrong answer only 1/Nth of the time. Which is quite good. There might be other solutions that are better ... and I am aware of that. Here it is more about the journey than the destination. – ɭɘ ɖɵʊɒɼɖ 江戸 Aug 19 '13 at 9:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.