2D Packing a billion rectangles in less than 10 minutes
--D. Thiebaut (talk) 11:48, 21 August 2014 (EDT)
2D Packing a billion rectanglesD. Thiebaut, Aug. 21, 2014
This journal paper extends the conference paper "2D-Packing on a Large Scale" which I presented in Lisbon, Portugal, at INFOCOMP 2013. The paper was one of a few papers receiving "Best Paper Award," and describes a heuristic for 2D-packing rectangles in a large rectangular frame. My application is that of packing a large collection of images, such as Wikipedia's 3 million images, on large displays. The images packed have different sizes that are set depending on some parameter, such as the number of views, or the popularity of the pages on which they appear.
Abstract of the paper: "We present a novel heuristic for 2D-packing of rect- angles inside a rectangular area where the aesthetics of the resulting packing is amenable to generating large collages of photographs or images. The heuristic works by maintaining a sorted collection of vertical segments covering the area to be packed. The segments define the leftmost boundaries of rectangular and possibly overlapping areas that are yet to be covered. The use of this data structure allows for easily defining ahead of time arbitrary rectangular areas that the packing must avoid. The 2D-packing heuristic presented does not allow the rectangles to be rotated during the packing, but could easily be modified to implement this feature. The execution time of the present heuristic on various benchmark problems is on par with recently published research in this area, including some that do allow rotation of items while packing. Several examples of image packing are presented. A multithreaded version of our core packing algorithm running on a 32-core 2.8 GHz processor packs a billion rectangles in under 10 minutes."
- Read more here...
