Karger's algorithm for bin-packing?

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.

• i think, your question was answered here gamedev.stackexchange.com/questions/2829/…
– c69
Commented Aug 18, 2013 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. Commented Aug 19, 2013 at 9:48