Efficient Packings of Unit Squares in a Large Square
- PDF / 599,313 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 188 Views
Efficient Packings of Unit Squares in a Large Square Fan Chung1 · Ron Graham2 Received: 22 April 2018 / Revised: 8 February 2019 / Accepted: 28 March 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract How efficiently can a large square of side length x be packed with non-overlapping unit squares? In this note, we show that the uncovered area W (x) can be made as small as√ O(x 3/5 ). This improves an earlier estimate which showed that W (x) = O x (3+ 2)/7 log x . Keywords Square packing · Optimization · Tiling Mathematics Subject Classification 52C15
1 Introduction Given a large square S(x) of side length x, let W (x) denote the minimum possible amount of uncovered area in any packing of S(x) with non-overlapping unit squares. When x = N is an integer, then of course W (N ) = 0. However, when x is not an integer, then some waste (= uncovered area) is inevitable. If we naively pack the square in the “obvious” way (see Fig. 1), then the wasted area will be proportional to x(x − x), which is linear in x when x − x is bounded away from 0. During the past 40 years, better upper bounds for W (x) have been obtained. Beginning with the Montestimate W (x) = O(x 7/11 ) = O(x 0.63636... ) from [3], this was improved by √ 3)/2 (3− ) = gomery (Montgomery, H.: Personal communication) to W (x) = O(x
Dedicated to the memory of Ricky Pollack. Editor in Charge: János Pach Fan Chung [email protected] Ron Graham [email protected] 1
Department of Mathematics, University of California, San Diego, USA
2
Department of Computer Science and Engineering, University of California, San Diego, USA
123
Discrete & Computational Geometry √
(3+ 2)/7 log x) by the authors O(x 0.63397... ) and √ then most recently to W (x) = O(x [2] where (3 + 2)/7 = 0.63060 . . . In the other direction, a seminal result of Roth and Vaughan [7] shows that if x(x − x) > 1/6 then
W (x) > 10−100 x x
(1)
where x denotes the distance from x to the nearest integer. In particular, this shows that W (x) > cx 1/2 for some absolute constant c provided x is bounded away from an integer. In this note, we improve the upper bound for W (x). Theorem 1.1 W (x) = O(x 3/5 ). To prove Theorem 1.1, we will describe the packing procedure in three stages. In the first stage, we partition the square S(x) into a perfect square (of integral side) and two rectangles. In second stage, the rectangles are packed by stacks of unit squares but some trapezoids are still left uncovered as well as some tiny triangles along the edges. At the last stage, we pack the trapezoids in a careful way. We note that in the first and second stages, the strategy for packing S(x) will be similar to that used in [2], although the parameters are chosen differently. In each stage, there are a number of steps to pack unit squares into the regions. During this process, we will keep track of the waste in each step of the way. All together, we will consider nine types of waste, denoted by Wi (x) for i = 1, . . . , 9. We will show that for each i, Wi (x) = O(x 3/5 ). Su
Data Loading...
