Abstract
Let S be a set of n points in the unit square [0,1]2, one of which is the origin. We construct n pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in S, and the rectangles jointly cover at least a positive constant area (about 0.09). This is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ponder this challenge: puzzle for June 2004; http://domino.research.ibm.com/comm/wwwr_ponder.nsf/Challenges/June2004.html.
M. Abramovitz and I. Stegun: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Dover, New York, 1964.
N. Bansal, A. Caprara and M. Sviridenko: A new approximation method for set covering problems, with applications to multidimensional bin packing, SIAM J. Comput. 39 (2009), 1256–1278.
N. Bansal, J. Correa, C. Kenyon and M. Sviridenko: Bin packing in multiple dimensions: inapproximability results and approximation schemes, Math. Operat. Research 31 (2006), 31–49.
N. Bansal, X. Han, K. Iwama, M. Sviridenko and G. Zhang: A harmonic algorithm for the 3D strip packing problem, SIAM J. Comput. 42 (2013), 579–592.
A. Caprara: Packing 2-dimensional bins in harmony, in: Proc. 43rd FOCS, IEEE, 2002, 490–499.
A. Caprara: Packing d-dimensional bins in d stages, Math. Oper. Res. 33 (2008), 203–215.
M. Chlebĺk and J. Chlebĺková: Hardness of approximation for orthogonal rectangle packing and covering problems, J. Discrete Alg. 7 (3) (2009), 291–305.
T. Christ, A. Francke, H. Gebauer, J. Matousek and T. Uno: A doubly exponentially crumbled cake, Electronic Notes in Discrete Mathematics 38 (2011), 265–271.
H. T. Croft, K. J. Falconer and R. K. Guy: Unsolved Problems in Geometry, volume II of Unsolved Problems in Intuitive Mathematics, Springer, New York, 1991.
P. Erdős and R. L. Graham: Note on packing squares with equal squares, J. Combin. Theory Ser. A 19 (1975), 119–123.
R. Harren, K. Jansen, L. Prädel and R. van Stee: A (5=3+ε)-approximation for strip packing, Comput. Geom. 47 (2014), 248–267.
R. Harren, K. Jansen, L. Prädel, U. M. Schwarz and R. van Stee: Two for one: tight approximation of 2D bin packing, Int. J. Found. Comput. Sci. 24 (2013), 1299–1328.
K. Jansen and R. Solis-Oba: A polynomial time approximation scheme for the square packing problem, in: Proc. 13th IPCO, vol. 5035 of LNCS, Springer, 2008, 184–198.
K. Jansen and G. Zhang: Maximizing the total profit of rectangles packed into a rectangle, Algorithmica 47 (3) (2007), 323–342.
L. Prädel: Approximation algorithms for two-dimensional geometrical knapsack, Masters thesis, Department of Computer Science, University of Kiel, 2008.
I. Schiermeyer: Reverse-fit: a 2-optimal algorithm for packing rectangles, in: Proc. 2nd ESA, vol. 855 of LNCS, Springer, 1994, 290–299.
A. Steinberg: A strip-packing algorithm with absolute performance bound 2, SIAM J. Comput. 26 (2) (1997), 401–409.
W. Tutte: Recent Progress in Combinatorics: Proceedings of the 3rd Waterloo Conference on Combinatorics, May 1968, Academic Press, New York, 1969.
P. Winkler: Packing rectangles, in: Mathematical Mind-Benders, A. K. Peters Ltd., Wellesley, MA, 2007, 133–134.
P. Winkler: Puzzled: rectangles galore, Communications of the ACM 53 (11) (2010), 112.
P. Winkler: Puzzled: solutions and sources, Communications of the ACM 53 (12) (2010), 128.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appeared in the Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms, (SODA 2012), Kyoto, Japan, January 2012.
Supported in part by the NSF grant DMS-1001667.
Supported in part by the NSERC grant RGPIN 35586 and the NSF grant CCF-0830734.