If you are not familiar with CSS sprites, I can think of no better place for an introduction than this article on A List Apart. In short, you place many images into one image file, and then use that image as a background image and modify its position using background-position attributes. The only problem with the process is that its quite laborious, and really is robot work. While I was working on some html design a few weeks ago I became frustrated at this process, so I decided to figure out a way to automate it.
Now, admittedly, there already exist a few CSS sprite generators on the Internet, but in my opinion they left something to be desired. The big reason to create CSS sprites is to cut down on relatively sizable http requests (in comparison to the small images they may be requesting), in favor of one image that will be cached on the client side. A sweet side effect of this is that rollover images states don't require any JavaScript client-side code to preload any images, the browser takes care of it in the original image download. The problem is, in my experience, the existing generators don't actually save any bandwidth. By inefficiently placing the images into the output image they actually end up adding a bit too much to the final image output size. While doing research as to how to minimize the output of such an image placement algorithm I ran headfirst into a fun computational challenge. The problem is a NP-Hard computation that is known as the bin packing problem. Fortunately, placing images that I have a list of is known as an 'offline' bin packing problem, meaning that I have the full set of inputs and I can generate a relatively decent output image from it.
When I was researching how to place the images, I read a great series of e-mails from a mailing list in which Clive Tooth explains an intuitive algorithm:
The new method works by sub-dividing the remaining part of the original rectangle into sub-rectangles and then, when a new square is to be inserted, choosing one of the subrectangles which will completely hold the square and then positioning the square at the top left hand corner of the rectangle. The remaining L-shaped part of the rectangle is then partitioned into two rectangles. Occasionally one of the two new rectangles may have a zero height or zero width, but this does not matter. Thus at each stage one rectangle is used and replaced by two smaller rectangles. Thus, just before inserting piece n, the remaining space will have been split into n rectangles. So, we would need to prove that at that stage at least one of the rectangles had a short side of least 1/n.
In short, as long as you have the correct size to output to, you can place a rectangle inside that output with decent efficiency. In further research I found that the output image was proven to never be more than 70% inefficient, but in practice in my tests it's actually been much closer to 20% or so. I also created my own algorithm for generating an estimate output rectangle size for containing a list of images, that seems to correctly guess the output size.
Within a few days I hope to show some code, but for now here is a little taste of the output of 16x16 images from the awesome silk icon set:
Note that this doesn't show any of the more intricacies of the algorithm, but it does show where I'm going with it.