key: cord-0633360-n6pc7n4n
authors: Aamand, Anders; Abrahamsen, Mikkel; Beretta, Lorenzo; Kleist, Linda
title: Online Sorting and Translational Packing of Convex Polygons
date: 2021-12-07
journal: nan
DOI: nan
sha: c33d8ed8ba340f913b53864957cd39fa482eee6a
doc_id: 633360
cord_uid: n6pc7n4n

We investigate various online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container before the next piece is revealed; the pieces must not be rotated, but only translated. The aim is to minimize the used space depending on the specific problem at hand, e.g., the strip length in strip packing, the number of bins in bin packing, etc. We draw interesting connections to the following online sorting problem OnlineSorting{}$[gamma,n]$: We receive a stream of real numbers $s_1,ldots,s_n$, $s_iin[0,1]$, one by one. Each real must be placed in an array~$A$ with $gamma n$ initially empty cells without knowing the subsequent reals. The goal is to minimize the sum of differences of consecutive reals in $A$. The offline optimum is to place the reals in sorted order so the cost is at most $1$. We show that for any $Delta$-competitive online algorithm of OnlineSorting{}$[gamma,n]$, it holds that $gamma Delta inOmega(log n/log log n)$. We use this lower bound to prove the non-existence of competitive algorithms for various online translational packing problems of convex polygons, among them strip packing, bin packing and perimeter packing. This also implies that there exists no online algorithm that can pack all streams of pieces of diameter and total area at most $delta$ into the unit square. These results are in contrast to the case when the pieces are restricted to rectangles, for which competitive algorithms are known. Likewise, the offline versions of packing convex polygons have constant factor approximation algorithms. On the positive side, we present an algorithm with competitive ratio $O(n^{0.59})$ for online translational strip packing of convex polygons. In the case of OnlineSorting{}$[C,n]$ for any constant $C>1$, we present an $O(2^{O(sqrt{log nloglog n})})$-competitive algorithm.

Packing problems are omnipresent in our daily lives and likewise appear in many large-scale industries. For instance, two-dimensional versions of packing arise when a given set of pieces have to be cut out from a large piece of material such that waste is minimized. This is relevant in clothing production where pieces are cut out from a strip of fabric, and similarly in leather, glass, wood, and sheet metal cutting. In these settings, it is often important that the inherent structure of the host material (grain of fabric, patterns, etc.) is respected, i.e., the pieces should not be arbitrarily rotated, but merely translated. In some applications, the objects appear in an online fashion, i.e., the pieces appear one after the other, and each of them must be placed before the next one is known. This is in contrast to offline problems, where all the pieces are known in advance. Problems related to packing were some of the first for which online algorithms were described and analyzed. Indeed, the first use of the terms "online" and "offline" in the context of approximation algorithms was in the early 1970s and used for algorithms for bin-packing problems [20] . Most existing research on packing, and all research on online translational packing that we are aware of, is concerned with axis-parallel rectangular pieces.

In this paper, we study online translational packing of convex polygons. The pieces arrive one by one and have to be placed irrevocably into a horizontal strip (or into bins, a square, the plane) before the next piece is revealed, and only translations of the pieces are allowed. The aim is to minimize the used space depending on the specific problem at hand, e.g., the used length of the strip, the number of bins, etc.

To develop lower bounds for these packing problems, we introduce the problem Online-Sorting[γ, n] which we believe to be of independent interest. In this problem, we have an empty array A with γn cells, γ ≥ 1, and receive a stream of real numbers s 1 , . . . , s n , s i ∈ [0, 1]. Each real has to be placed into an empty cell of A before the next real is known. The goal is to minimize the sum of differences of consecutive reals in A. The offline optimum is obtained by placing the reals in sorted order in some n cells of A. We show that Online-Sorting does not allow for constant factor competitive online algorithms.

Theorem 1. Suppose that γ, ∆ ≥ 1 are such that Online-Sorting[γ, n] admits a ∆-competitive algorithm, then γ∆ = Ω(log n/ log log n).

We then use this insight to show that various packing problems do not allow for constant factor asymptotically competitive online algorithms. In Strip-Packing, we have a horizontal strip of height 1 which is bounded to the left by a vertical segment and unbounded to the right. The goal is to place the pieces so that we use a part of the strip of minimum length. In Bin-Packing, the pieces have to be placed in unit squares, and the goal is to use a minimum number of these squares. In Perimeter-Packing, we can place the pieces anywhere in the plane, and the goal is to minimize the perimeter of their convex hull. In Square-Packing[δ], we receive a stream of pieces with diameter at most δ and total area at most δ, and the goal is to place them in a unit square. For more background on each of these packing problems and their relation to previous work, we refer to Section 1.2.

Theorem 2. The following holds, where n is the number of pieces:

(a) Strip-Packing does not allow for a competitive online algorithm, even if all pieces have diameter at most δ for any constant δ > 0. In particular, the competitive ratio of any algorithm is Ω( log n/ log log n).

(b) Bin-Packing does not allow for a competitive online algorithm, even if all pieces have diameter at most δ for any constant δ > 0. In particular, the competitive ratio of any algorithm is Ω( log n/ log log n).

(c) Perimeter-Packing does not allow for a competitive online algorithm, even if all pieces have diameter at most δ for any constant δ > 0. In particular, the competitive ratio of any algorithm is Ω( 4 log n/ log log n).

(d) Square-Packing[δ] does not allow for an online algorithm for any δ ∈ (0, 1]. In particular, for any algorithm and infinitely many n, there exists a stream of n pieces of total area O( log log n/ log n) that the algorithm cannot pack in the unit square.

Here, (a) and (b) even hold in the asymptotic sense, i.e., if we restrict ourselves to instances with offline optimal cost at least C, for any constant C > 0.

On the positive side, we present online algorithms for both online sorting and strip packing. For Online-Sorting[γ, n], we distinguish two scenarios: the case without any extra space, i.e., γ = 1, and the case γ = 1 + ε a constant ε > 0. In the case γ = 1, we can provide an asymptotically tight analysis. Theorem 3. There exists an online algorithm for Online-Sorting [1, n] with competitive ratio at most 18 √ n. Every online algorithm of Online-Sorting [1, n] has competitive ratio at least n/2.

As we describe in Section 1.3, this can be seen as an asymptotically tight analysis of an online version of the travelling salesperson problem (TSP) on the real line. Indeed, we can imagine that we must visit n cities on [0, 1] at time steps 1, . . . , n. The position of each city is revealed to us in an online fashion and we immediately have to decide the time step where we visit this city. In addition to packing and TSP, we believe that the online sorting problem can be useful when studying other online problems as well.

In contrast to Theorem 3, when the available space is a constant factor larger than n, there exists an algorithm with competitive ration n o (1) . We note that there is an exponential gap between the lower and upper bounds in Theorem 1 and Theorem 4. It is an interesting open problem to close this gap, say for Online-Sorting [2, n] .

There is a trivial n-competitive algorithm Strip-Packing that places each of the n pieces as deep into the strip as possible. Improving upon this turns out to be quite challenging. We present an online algorithm with competitive ratio O(n log 3−1 log n) = O(n 0.59 ), where log x denotes the base-2 logarithm of x. Another interesting open problem is to improve upon this. Is it for example possible to obtain an n o(1)competitive algorithm for Strip-Packing as we have for Online-Sorting[1 + ε, n]? Because the sorting problem is much simpler than the packing problem, the lower bound from Theorem 1 implies a lower bound for Strip-Packing, but the algorithm behind Theorem 4 does not lead to any packing algorithm.

Our results in Theorem 2 are in contrast to translational offline packing of convex polygons for which constant factor approximations exist. In a recent paper, Alt, de Berg, and Knauer [5, 6] gave a constantfactor approximation algorithm for offline translational packing of convex polygons so as to minimize the area of their bounding box. The algorithm works by first grouping the pieces into exponentially increasing height classes and then sorting the pieces in each height class by the slopes of their spine segments; see Figure 1 . The spine segment of a piece is the line segment from the bottommost to the topmost corner. Placing the pieces in rows in this sorted order (so that each row appears as a fan-like pattern) yields a compact packing with constant density. We show that similar procedures yield constant factor approximations for the offline version of strip packing, bin packing, square packing and perimeter packing. (d) Offline-Square-Packing [1/10] , in particular, every set of convex polygons of diameter and total area at most 1/10 can be packed into the unit square.

The contrast between Theorem 2 and Theorem 6 shows that sorting the pieces by the slope of their spine segments is essential for obtaining an efficient packing. In particular, we use the lower bound from Theorem 1 to create an adaptive stream of pieces that will force any packing algorithm to use excessive space. In the reduction, the numbers to be sorted in the online sorting problem correspond to the slopes of the spine segments in the packing problems, and the impossibility of placing the numbers in nearly sorted order implies that the packing algorithm is forced to produce an arrangement that is far from an optimal fan-like pattern.

The literature on online packing problems is vast. See the surveys of Christensen, Khan, Pokutta, and Tetali [13] , Epstein and van Stee [17] , van Stee [41, 42] , and Csirik and Woeginger [15] for an overview. Below we survey the most important results for each of the types of packing problems mentioned in Theorem 2. Let us highlight that when the pieces are restricted to axis-parallel rectangles, there are online algorithms with constant competitive ratios solving all the problems of Theorem 2.

Strip packing. In strip packing, we have a horizontal strip of height 1 bounded by a vertical segment to the left but unbounded to the right. The goal is to place the pieces in the strip so as to minimize the length of the part of the strip that has been used. Milenkovich [34] and Milenkovich and Daniels [35] described exact algorithms for offline strip packing where the pieces are simple or convex polygons.

Baker and Schwarz [9] described the first algorithms for online strip packing of rectangular pieces. The FFS (First Fit Shelf) algorithm has a competitive ratio of 6.99 under the assumption that the height of each rectangle is at most 1. Ye, Han, and Zang [43] improved the algorithm and obtained a competitive ratio of 7 /2 + √ 10 ≈ 6.6623 without the restriction on rectangle heights. Restricting the attention to large instances, FFS has an asymptotic competitive ratio that can be made arbitrarily close to 1.7. Csirik and Woeginger [16] described an improved algorithm with an asymptotic competitive ratio arbitrarily close to h ∞ ≈ 1.69103. This was later improved to 1.58889 by Han, Iwama, Ye, and Zhang [24] . In contrast, we show that when the pieces are convex polygons, then no competitive algorithm exists (Theorem 2 (a)).

Bin packing. In bin packing, we have an unbounded supply of identical containers, and the goal is to pack the pieces into as few containers as possible. As mentioned, online bin packing problems have been studied since the early 1970s [20] . Many papers have been devoted to the study of online translational bin packing axis-parallel rectangular pieces into unit square bins. In long sequences of papers, the upper bound on the asymptotic competitive ratio for this problem has been decreased from 3.25 to 2.5545 and the lower bound has been increased from 1.6 to 1.907 [23] . In this paper, we show that when packing convex polygons instead of axis-parallel rectangles, there is no competitive algorithm (Theorem 2 (b)).

Perimeter packing. In some packing problems, the "container" has no predefined boundaries (contrary to the cases of strip and bin packing and the study of critical densities), but the pieces can be placed anywhere in the plane and the container is dynamically updated as the bounding box or the convex hull of the pieces. The goal is then to minimize the size of the container. In 2D versions of this problem, natural measures of size are the area or the perimeter of the container. Many papers have been written about offline versions of these problems [2, 4, 5, 8, 14, 18, 29, 30, 31, 33, 34, 35, 37, 40] .

Online versions have received relatively little attention. Fekete and Hoffmann [19] studied online packing axis-parallel squares so as to minimize the area of their bounding square, and gave an 8-competitive algorithm for the problem. Abrahamsen and Beretta [1] gave a 6-competitive algorithm for the same problem and studied the more general case where the pieces are axis-parallel rectangles and we want to minimize the bounding box, with or without rotations by 90 • allowed. They gave a 3.98-competitive algorithm for minimizing the perimeter and showed that there exists no competitive algorithm for minimizing the area, when the pieces can be arbitrary rectangles.

If the pieces are convex polygons that can be arbitrarily rotated, then the minimum perimeter problem can be reduced to the case of packing axis-parallel rectangles by first rotating each piece so that a diameter of the piece is horizontal. Then the density of the piece in its axis-parallel bounding box is at least 1/2, and the algorithm for rectangles can be applied to the bounding box. An interesting question that remained open was therefore whether there is a competitive algorithm for minimizing the perimeter when the pieces are convex polygons that can not be rotated. We answer this question in the negative (Theorem 2 (c)).

Critical densities and square packing. The study of critical densities dates back at least to the 1930s. In the famous Scottisch Book [32] , Auerbach, Banach, Mazur and Ulam gave the following theorem (slightly rephrased) and corollary without a proof.

Theorem (Potato Sack Theorem, [32] ). If {K n } ∞ n=1 is a sequence of convex bodies in R 3 , each of diameter ≤ δ and the sum of their volumes is ≤ V , then there exists a cube with sidelength s = f (δ, V ) such that all the given bodies can disjointly be placed into it when rotations are allowed.

Corollary. One kilogram of potatoes can be put into a finite sack.

A simple proof of the theorem, generalized to an arbitrary dimension, was given by Kosiński [27] . It was asked in [32] to determine the function f (δ, V ), which, in modern terms, means to determine the critical density. That is, to find the largest value of V such that a sequence of convex bodies of diameters at most δ and total volume V can always be placed in the unit cube. This theorem has sprouted a lot of interest in determining critical densities in various settings. For instance, Moon and Moser [36] proved that any sequence of d-dimensional cubes of total volume 1/2 d−1 can be packed into the unit cube. As two cubes with sidelengths 1/2 + ε, for any ε > 0, cannot be packed in the unit cube, this shows that the critical density of packing cubes into a unit cube is 1/2 d−1 for any d ≥ 1. Alt, Cheong, Park, and Scharf [7] showed that there exist n 2D unit disks embedded in 3D (with different normal vectors) such that whenever they are placed in a non-overlapping way, their bounding box has volume Ω( √ n). It follows that when rotations are not allowed, the critical density of packing convex bodies of bounded diameter into a cube is 0, or, in other words, that one kilogram of potatoes cannot always be put into a finite sack by translation. In contrast to this, the critical density of packing convex polygons of bounded diameter into the unit square by translation is positive when the diameter is sufficiently small, as we prove in Theorem 6 (d).

The study of critical densities likewise makes sense when the pieces appear in an online fashion. A lower bound on the critical density of online packing squares into the unit square has been improved in a sequence of papers [11, 19, 25, 26] from 5/16 [26] to 2/5 [11] . Interestingly, Januszewski and Lassak [26] proved that in dimension d ≥ 5, the critical density of online packing cubes into the unit cube is 1/2 d−1 , just as in the offline case.

Lassak and Zhang [28] proved that the Potato Sack Theorem also holds for any dimension d ≥ 1 when the convex bodies appear online, if rotations are allowed. In order to achieve this, each convex body of volume V is rotated so that it has an axis-parallel bounding box of volume at most d! · V . The problem is therefore reduced to online packing axis-parallel boxes. In simplified terms, it is then proved that for some constant δ = δ(d) > 0, any sequence of axis-parallel boxes of diameter and total area at most δ can be packed online in the d-dimensional unit hypercube. Determining whether the critical density of translational and online packing convex 2D polygons is positive remained an interesting question: On one hand, this packing problem is harder than the 2D offline version which has positive critical density (Theorem 6 (d)), and on the other hand, it is easier than the 3D online version which has 0 critical density (since also the 3D offline version has 0 critical density [7] ). In this paper, we prove that the 2D online version also has critical density 0 (Theorem 2 (d)).

Theorem 3 can be seen as an asymptotically tight analysis of the traveling salesperson problem (TSP) on the real line, following the online-list paradigm: We want to visit n cities in the unit interval [0, 1] over the course of n days, one city per day. The positions of the cities are revealed sequentially to us in an online fashion, and for each city, we have to immediately decide which day to visit that city. Our goal is to minimize the total distance travelled. In fact, we could equally well imagine that we had γn days for our tour which corresponds to Online-Sorting[γ, n].

The usually studied version of online TSP follows the online-time paradigm. Here, a server starts at point 0 at time 0 and moves with at most unit speed. Each request σ i = (t i , r i ) is revealed at some time t i and should be visited by the server at time r i or later. We want to minimize the time before the server has visited all requests σ 1 , . . . , σ n . This problem has been intensely studied [10] . The distinction between these two paradigms is common in the area of scheduling, but the online-list variant of TSP has apparently not received any attention so far.

Fiat and Woeginger [21] studied a scheduling problem following the online-list paradigm that seems particularly related to online sorting: The goal is to minimize the average job completion time in a system with n jobs and a single machine. In every step, a single new job arrives and must be scheduled to its time slot immediately and irrevocably and without knowledge of the jobs that arrive in later steps. The offline optimum is to schedule the jobs according to their processing times in sorted order. It was shown that no algorithm can be log n-competitive, but that there is a O(log 1+ε n)-competitive algorithm for all ε > 0. For surveys on (online) scheduling, see [3, 12, 22, 38, 39 ].

In Section 2, we introduce our terminology and notation. In Section 3, we describe the connection between the problems of online sorting and online strip packing. In Section 4, we analyze the online sorting problem and prove Theorems 1, 3 and 4. In Section 5, we study online packing problems and present proofs for Theorems 2 and 5. Finally, in Section 6, we consider the offline versions of the packing problems and prove Theorem 6. See Figure 2 for an overview of the reductions we make.

Strip-Packing

Perimeter-Packing Figure 2 : An overview of our reductions. Note that an arrow from problem A to problem B means that an algorithm for B implies an algorithm for A. Here, Ø ≤ δ means that the diameter of each piece is at most an arbitrary constant δ > 0.

In the online problems studied in this paper, the input is a stream σ 1 , . . . , σ n of objects, and we need to handle each object σ i before we know the next ones σ i+1 , . . . , σ n . Here, objects are either real numbers from the unit interval [0, 1], in which case we call them reals, or they are convex polygons, in which case we call them pieces. The problems will be defined in more detail in Section 3.

Let us now revisit the standard terminology of competitive analysis for an online algorithm A of a minimization problem P. For any instance I of P, let OPT(I) denote the cost of the offline optimum solution and A(I) denote the cost of the solution that A produces on input I. Let f be a function from the set of instances to the real numbers (the functions f we consider will in fact only depend on n, the number of pieces in I). We say that A has (absolute) competitive ratio f (I) if for all instances I it holds that

If A has competitive ratio f (I) ≤ c for some constant c, then we say that A is competitive.

Similarly, we say that A has asymptotic competitive ratio f (I) if there exists β > 0 such that for all instances I it holds that

For a point p ∈ R 2 , we denote by x(p) and y(p) the x-and y-coordinates of p, respectively. For a compact set of points S ⊂ R 2 , we define the diameter of S as max p,q∈S |p − q|. We furthermore define the width and height of S as width(S) := max

If S is a polygon, we denote the area of S as area(S). A parallelogram P is horizontal if P has a pair of horizontal edges. The horizontal edges of P are then called the base edges. The shear of a horizontal parallelogram P is x(t) − x(b), where t and b are the top and bottom endpoints of a non-horizontal edge of P , respectively.

In (translational) Strip-Packing, we have a horizontal strip S of height 1 which is bounded to the left by a vertical segment and unbounded to the right; see Figure 3 . We have to pack a stream of convex polygonal pieces appearing online. We must place each piece before we know the next. Specifically, each piece must be placed in S by a translation such that it is interior disjoint from all previously placed pieces. The occupied part of S is the part from the left end of S to the vertical line through the rightmost corner of a piece placed in S. The width or the cost of a packing is the width of the part of S that is occupied, i.e., the horizontal distance from the left end of S to the rightmost corner of a piece placed in S. In the problem Online-Sorting[γ, n], we are given an array A with γn cells. Each arriving real is contained in the unit interval [0, 1]. After all n reals have been placed, define r := (r 1 , . . . , r n ) to be the numbers according to their left-to-right order in A. Furthermore, define the sentinel values r 0 := 0 and r n+1 := 1. Then the cost is given by

The offline optimum is achieved when the reals are in sorted order and is then exactly 1. Figure 2 gives an overview of reductions we make. Arguably, the crucial reduction is that from Online-Sorting to Strip-Packing, as described by the following lemma. Proof. Suppose that we have a C-competitive algorithm A 1 for Strip-Packing. Let s 1 , . . . , s n , s i ∈ [0, 1], be a stream of reals that we wish to sort online in an array A of size 2Cn. For each real s i , we construct a parallelogram P i with height 1, base edges of length 1/n, and shear s i . We then present A 1 with P i and observe where the bottom left corner of P i is placed in the strip. Let x i be the x-coordinate of this corner (suppose that the line x = 0 forms the left boundary of the strip). We then place s i in the cell of index nx i in the array A, and denote the resulting algorithm A 2 . Since the base segments of the parallelograms have length 1/n, this will not cause any collisions in A.

By sorting the pieces P 1 , . . . , P n in order of increasing shear and placing them in this order in the strip, we obtain a packing of width at most 2, so A 1 will place all pieces within a prefix of size 2C × 1 of the strip. Hence, A 2 will place each real in A. Let r := (r 1 , r 2 , . . . , r n ) be the numbers in the resulting left-to-right order in A produced by A 2 , and let P i be the parallelogram corresponding to r i . We have the following contributions to the width of the resulting packing; see also Figure 4 .

• Between the vertical left boundary of the strip and the top edge of P 1 , there is a gap of length at least

• If r i ≤ r i+1 , then there is a gap between the top edges of P i and P i+1 of length at least |r i+1 − r i |.

• If r i > r i+1 , then there is a gap of length at least |r i+1 − r i | between the bottom edges of P i and P i+1 .

• The bottom base edges of the pieces have total length 1 ≥ |r n+1 − r n |.

The sum of all these gaps is at least cost(r), and as half of the sum appear as distances along the top or the bottom edge bounding the strip, we get that the width of the produced packing is at least cost(r)/2. Now, since A 1 is C-competitive, we get that cost(r)/2 ≤ 2C, and hence cost(r) ≤ 4C.

In this section, we present upper and lower bounds for the online sorting problem. As a warm up, we consider in Section 4.1 the case where we have no extra space, i.e., we are given n reals in [0, 1] in an online fashion to be inserted into an array of length n. We prove Theorem 3, which gives an asymptotically tight analysis of the optimal competitive ratio in this case. In Section 4.2, we proceed to prove Theorem 1, thereby obtaining a general lower bound on the competitive ratio for Online-Sorting[γ, n]. Finally, in Section 4.3, we give an upper bound on the competitive ratio of Online-Sorting[γ, n] for γ > 1.

For online sorting n numbers in an array A of size n, we can prove asymptotically tight bounds on the optimal competitive ratio. 1 We restate Theorem 3 below.

Theorem 3. There exists an online algorithm for Online-Sorting [1, n] with competitive ratio at most 18 √ n. Every online algorithm of Online-Sorting [1, n] has competitive ratio at least n/2.

Proof. We start out by proving the lower bound. Let N := √ 2n . Consider a fixed but arbitrary online algorithm A. We are taking the role of the adversary and present reals of the form k /N with k = 0, 1, . . . , N . Clearly, if all reals are placed in an increasing fashion, the resulting cost is 1. This is the value A has to compete against.

For a partially filled array, a real is expensive if it does not appear in a cell with an empty adjacent cell. Our strategy is as follows. While there exists one, we present an expensive real. If we are able to present n expensive reals, then any two consecutive entries are distinct and differ by at least 1 /N. Consequently, the cost is at least n+1 N ≥ n/2. On the other hand, if we reach a point where no real of the form k /N is expensive, we present 0's until all entries are filled. Then, any real of the form k /N will appear next to a 0 in the array, so the total cost is at least N k=0 k /N = (N + 1)/2 > n/2.

Next we describe an algorithm A for Online-Sorting [1, n] with competitive ratio at most 18 √ n. Define and partition the array A into N 2 subarrays of contiguous cells, A 1 , . . . , A N2 , each of size either n/N 2 or n/N 2 . Whenever A receives a real x ∈ J i , it checks whether there exists a j such that A j is not full and already contains a number from J i . If so, A places x in the leftmost empty cell of A j . Otherwise, A checks if there exists a j such that A j is empty. If so, A places x in the leftmost cell of such an A j . Finally, if neither of the two above cases occur, then A recurses on the subarray formed by the union of the empty cells of A.

Ignoring the sentinel values r 0 := 0 and r n+1 := 1, we prove by induction on n that the total cost never exceeds

This clearly holds for n ≤ α 2 , as then T (n) ≥ n which is a trivial upper bound on the total cost. So let n > α 2 and assume inductively that the result holds for arrays of length n < n. Let B ⊂ {1, . . . , n} denote the set of indices i such that A[i] is full when the algorithm recurses for the first time. At this point, at most N 1 − 1 of the N 2 := 2N 1 subarrays A 1 , . . . , A N2 can be not completely filled, and each subarray must contain at least one real. In particular, |B| ≥ n/2. Let

The total cost incurred by the algorithm is then T 1 + T 2 . By the induction hypothesis, T 1 ≤ T (|B c |) ≤ T ( n/2 ). Furthermore, we can upper bound T 2 as

Here the first term comes from consecutive entries internal to a subarray that are both filled before the algorithm recurses for the first time (these have pairwise distance at most 1/N 1 ). 

It is easy to check that including the sentinel values, the total cost incurred by the algorithm never exceeds 18 √ n. This completes the proof.

We remark that the constant 18 in Theorem 3 can be significantly reduced by optimizing over N 1 and N 2 and using less crude bounds. We have abstained from doing so in order to obtain a simple exposition.

Having dealt with the case where we have no extra space, we turn to the setting where the array has length γn for some γ > 1. This is the setting which is important for our reductions to the online packing problems. In the following two sections, we prove lower and upper bounds, respectively, on how good online sorting algorithms can perform in this case.

Let us restate our lower bound for the competitive ratio of any algorithm for Online-Sorting[γ, n], γ ≥ 1.

Theorem 1. Suppose that γ, ∆ ≥ 1 are such that Online-Sorting[γ, n] admits a ∆-competitive algorithm, then γ∆ = Ω(log n/ log log n).

Before delving into the proof, we first describe the high level idea on how to generate an adversarial stream that incurs a high cost for any given algorithm. Assume for simplicity that γ is a constant, e.g., γ = 2 and that we want to prove a lower bound of ∆ on the total cost for some ∆ = (log n) Θ(1) . We will start by presenting the algorithm with reals coming from a set S of the form S = {i/n 0 | 0 ≤ i ≤ n 0 } for some n 0 ≤ n. At any point, we consider the set of maximal intervals of empty cells of the array, call them I 1 , . . . , I . For each real x ∈ S, we define the home H(x) as the union of all such intervals I j such that placing x in I j incurs no extra cost, i.e., the first non-empty cell to the left or right of I j contains the real x. (In fact, we will be a little more generous in the actual proof and allow for some small extra cost). If |H(x)| < n ∆n0 for some x ∈ S, we simply present the algorithm with copies of x until one is placed outside H(x) and thus has distance at least 1/n 0 to its neighbours. This will essentially contribute a total cost of 1/n 0 to the objective function, i.e., an average cost of ∆/n per presented copy of x. Note that this is the correct average cost for a lower bound of ∆. However, it may well be the case that no such x ∈ S exists (the average size of H(x) for x ∈ S is ≈ γn/n 0 which is much larger). In this case, we coarsen the set S to a set S ⊂ S consisting of every s'th element of S for some s = polylog n and only present the algorithm with reals from S from this point on. Now for most x ∈ S, it holds that H(x) = O(n/n 0 ) and that the distance from x to any real in S is Ω(s/n 0 ). Intuitively, this means that filling up H(x) with elements from S has a high cost of s/n ∆/n per presented real. We prove that this implies that we can point to a 'deserted space' consisting of Ω(n/∆) empty cells, in which the algorithm can only place a negligible number of reals without incurring a large total cost of ∆. Now we continue the process starting with S . In each coarsening step, we specify a 'deserted space' of size Ω(n/∆) and we can importantly enforce that these spaces be disjoint. As the array has 2n cells in total, this coarsening can happen at most O(∆) times. To ensure that we can in fact perform this coarsening Ω(∆) times, we must ensure that s ∆ n, which in turn implies that ∆ = O(log n/ log log n).

Proof of Theorem 1. Let A denote any online algorithm for Online-Sorting[γ, n]. We may assume that n is sufficiently large and that γ ≤ log n/ log log n. We will present the algorithm with an (adaptive) stream that incurs a cost of Ω (log n/γ log log n). Let C ∈ [3, 4] be minimal such that s := log C n is an integer and define δ := log n 16Cγ log log n . For i ∈ N, we define

We also let i * ∈ N be maximal with s i * ≤ n. In other words, we define i * := log n/C log log n . Our adversarial stream will consist of several phases, where in phase i ≥ 1, we present A with reals coming from the set S i . By the end of each phase, we will mark a certain set of currently empty cells of the array. Suppose that we are at time t and in some phase i. For an empty cell p ∈ R t , we define N t (p) ⊂ [m] to be the set consisting of the first non-empty cell to the left and to the right of p. Thus |N t (p)| ≤ 2. Furthermore, for x ∈ S i , we define the home of x at time t to be the set

By construction, a cell of A can be contained in at most two homes. We say that the home of x is small at time t if |H t (x)| < s i δ . In this case, we say that x is expensive at time t. The adversarial stream is constructed in the phases (were we stop as soon as the array contains n reals). Note that s i * +2 /δ ≥ sn/δ > γn, so in phase i * + 2, the real 0 is always expensive and the process will therefore eventually stop.

We prove three lemmas below which combine to give our desired result.

If the algorithm does not terminate in phase i, then |D i | ≥ n 8δ .

Proof. We consider the situation in the end of a phase i where the algorithm has not terminated. Since for each x ∈ S i \ W i , we have H t (x) > 4γs i and a cell can lie in at most two homes, it follows that |S i \ W i | ≤ 2· γn 4γs i ≤ |S i |/2, and so |W i | ≥ |S i |/2. Now S i+1 can be obtained from S i by including every s'th elements from S i in increasing order starting with 0. If we define D i := x ∈ S i | ∀z ∈ S i+1 it holds that |z − x| ≥ s i+1 12n , it then follows that |D i | ≥ 3 4 |S i |. Here we used the assumption that i ≤ i * − 2 which implies that that S i consists of sufficiently many reals (at least s 2 ) for the bound to hold. It follows that |D i | = |W i ∩D i | ≥ |S i |/4. Again using that each cell is contained in at most two homes, we have that

Lemma 9. Let α > 0 and assume that the algorithm does not terminate in phase i. If at least 56αnγ/s reals from S i+1 are placed in D i , then the total cost is at least α.

Proof. Write D i = J as a disjoint union of maximal intervals of empty cells in D i . For each , we have that |J | ≤ 4γs i . If at least 56αnγ/s reals are placed in D i , it follows that at least 14αn/s i+1 of the intervals receive at least one real from S i+1 . For such an interval J , we have by the definition of a home, that one of the (up to two) non-empty cells immediately to the left and right of J contains a real x of distance at most s i 2n to an element of D i . However, any x ∈ S i+1 placed in J has distance at least s i+1 12n to any element of

14n , assuming that n and hence s are sufficiently large. Since the J are disjoint, it easily follows that the total cost is at least s i+1 14n · 14αn s i+1 = α. Lemma 10. If A assigns n 0 reals to unmarked cells, during phases 1, . . . , i * , then the total cost is at least δn0 4n − 1.

Proof. Write a i for the number of reals that the algorithm assigns to unmarked cells during phase i, so that i≤i * a i = n 0 . Let b i := ai s i /δ and c i := b i . We make the following claim.

Claim. The total cost is at least i≤i * c i · s i 2n . Proof of Claim. Note that during the while-loop of our algorithm, the assumption that the home of x is small implies that it must happen at least c i times during phase i that a real from S i is placed outside its home. When an real x gets placed in a cell p ∈ R t \ H t (x) outside its home, the reals stored in the cells in N t (p) have distance at least s i 2n to x. We say that an interval of cells [p 1 ,

We say that an i-jump [p 1 , p 2 ] and a j-jump [p 1 , p 2 ] are disjoint if (p 1 , p 2 ) ∩ (p 1 , p 2 ) = ∅. We will show that we can find a collection J of such jumps such that (1) the jumps in J are pairwise disjoint and (2) we can make a partition J = i≥1 J (i) such that J (i) contains at least c i i-jumps. The claim then follows immediately by the triangle inequality.

To show the existence of such a collection J , suppose we at step t in some phase i are given a collection of (≤ i)-jumps J t and a partition J t = j≤i J

consists of j-jumps. Suppose further that we place a real x in a cell p ∈ R t \ H t (x) at step t. Since x was placed outside of its home, any of the (up to two) intervals with one endpoint at p and the other at a cell of N t (p) will form an i-jump. Now if p is not contained in a jump of J t , we can easily extend to a collection J t+1 = j≤i J (j) t+1 which still satisfies (1) and where J (i) t+1 contains one further i-jump. We simply add the i-jump between p and either of its neighbours in N t (p). Suppose on the other hand that p is contained in a j-jump [q 1 , q 2 ] of J (j) t for some j ≤ i. In this case, we in particular have that |N t (p)| = 2 and we write N t (p) = {p 1 , p 2 } where p 1 < p 2 . Then [p 1 , p] and [p, p 2 ] are both i-jumps and in particular j-jumps for j ≤ i. We then replace [q 1 , q 2 ] with [p 1 , p] in J j t+1 and include [p, p 2 ] in J i t+1 to obtain a collection J t+1 = j≤i J (j) t+1 having the same number of j-jumps for j < i but one extra i jump compared to J t . The existence of the collection J follows immediately from these observations. Now assuming that n is sufficiently large, we have that b i ≥ δai 2s i . Moreover, using the definition of i * , it is easy to check that i≤i * s i ≤ 2n. Combining this with the claim, we can lower bound the total cost by

as desired.

We now combine the two lemmas to prove a lower bound on the cost incurred by the algorithm on our adversarial stream. Recall that C = 3 and δ = log n 16Cγ log log n . Suppose for contradiction that the algorithm has not terminated by the end of phase i * − 2. Using Lemma 8 and the fact that the sets (D j ) j≤i * −2 are disjoint, we obtain that

assuming that n is sufficiently large. This is a contradiction as there are only γn cells in A. Thus, the algorithm must terminate during some phase i 0 ≤ i * − 2. Now the algorithm must either place at least n/2 reals in marked cells or n/2 reals in unmarked cells. In the former case, there must be a phase i in which n 2i * reals a placed in D i , and hence it follows from Lemma 9 that the total cost is Ω( s i * γ ) = Ω(log n). In the latter case, it follows from Lemma 10 that the total cost is at least δ 8 − 1 = Ω log n γ log log n .

In this section, we design an algorithm that shows the following theorem. First, we prove a slightly more general lemma, and then we instantiate it with the right set of parameters to obtain Theorem 4.

Lemma 11. Let δ ∈ (0, 1/2) and [α, α + β) ⊆ [0, 1]. Then, for any k ≥ 1 with k ≤ 1/(2δ) + 1 there exists an algorithm that solves Online-Sorting [1 + 2kδ, n] over any stream of reals r 1 , . . . , r n ∈ [α, α + β) achieving a cost of β · n 1/(k+1) δ −O(k+1) .

Proof. We prove the statement by induction on k. The base case of k = 1 follows directly from Theorem 3: in fact, it is sufficient to apply the mapping x → α + βx to the reals in our stream and notice that the resulting cost also shrinks by a factor β. We call this version of the algorithm OnlineSorter 1 .

For the induction step, we define the algorithm OnlineSorter k using OnlineSorter k−1 as a subroutine. Let b := n 1/(k+1) , n := δn k/(k+1) and w := (1 + 2(k − 1)δ) · n . For i ≥ 1, we define the box 

is not full, we place x into B p(i) using OnlineSorter k−1 . Otherwise, we assign a new active box and set p(i) := max j∈[b] p(j) + 1, update A and R accordingly, and then place x into B p(i) using OnlineSorter k−1 .

By the inductive hypothesis, OnlineSorter k−1 can place n reals into an array of size w. Hence, to prove correctness we only have to ensure that the set of used boxes are contained in the array, i.e., that R ≤ (1 + 2kδ)n. We show that the total number of empty cells in [1, R] is at most 2kδn and therefore there must be n full cells in [ 

Moreover, |F | ≤ n /n and therefore i∈F E(B i ) ≤ n n · 2(k − 1)δ · n = 2(k − 1)δn.

If i ∈ E, we use the trivial bound E(B i ) ≤ w, moreover j ∈ E implies B j ∈ A, hence |E| ≤ b. This yields

Putting everything together, we obtain

where the last inequality holds because 2(k − 1)δ ≤ 1 by assumption on k.

We are left to bound the total cost for which we likewise use induction. By cost (k) (r 1 , . . . , r n ), we denote the cost incurred by algorithm OnlineSorter k when facing the stream of reals r 1 , . . . , r n . We prove that there exists C > 0 such that cost (k) (r 1 , . . . , r n ) ≤ β · n 1/(k+1) δ −C·(k+1) for any stream of reals r 1 , . . . , r n with r i ∈ [α, α + β). For k = 1, we already explained above how Theorem 3 implies that OnlineSorter 1 places a stream r 1 , . . . , r n ∈ [α, α + β) with a cost of cost (1) (r 1 , . . . , r n ) = 18β √ n, and we can choose C accordingly. Now suppose k > 1, and let {B 1 , . . . , B } be the set of full or active boxes. We have ≤ R/w ≤ (1 + 2kδ)n/w ≤ 3n 1/(k+1) δ −1 . We can think of our algorithm as partitioning the stream r 1 , . . . , r n into substreams according to the box in which each real is placed. For i ∈ [ ], denote the substream of length L i placed in B i with y i 1 , . . . , y i Li so that we have {r 1 , . . . , r n } = i=1 {y i 1 , . . . , y i Li }. Moreover, L i ≤ n for each i ∈ [ ]. Define α := (i−1)·βn −1/(k+1) and β := βn −1/(k+1) , then for each j ∈ [L i ] it holds α ≤ y i j < α +β . By the induction hypothesis, the cost induced by the recursive call of OnlineSorter k−1 on box B i is bounded by

Now we are ready to estimate the total cost of OnlineSorter k as the sum of costs generated inside a box B i or between any two consecutive boxes:

where the last inequality holds if we choose C large enough.

Finally, we can prove Theorem 4.

Proof of Theorem 4. We apply Lemma 11 choosing α := 0, β := 1, k := log n/ log log n and δ := ε/(2k). 

In this section, we consider various online packing problems. In Section 5.1, we show that Strip-Packing does not allow for a competitive online algorithm. In fact, the argument generalizes to the other important online packing problems Square-Packing, Perimeter-Packing and Bin-Packing. This holds even when all pieces have diameter less than an arbitrarily small constant δ > 0. In Section 5.2, we present an online algorithm for convex strip packing. A naive greedy algorithm for this problem places each new piece as deep into the strip as possible, and this algorithm is n-competitive, where n is the number of pieces. Our algorithm is O(n 0.59 )-competitive.

Theorem 1 and Lemma 7 yield the following corollary.

Corollary 12. Strip-Packing does not allow for a competitive online algorithm, even when the diameter of each piece is at most 2. Specifically, for every online algorithm A, there exists a stream of n parallelograms of diameter at most 2 such that A produces a packing of width Ω( log n/ log log n), while the optimal offline packing has width at most 2.

Proof. Suppose that Strip-Packing has a C-competitive algorithm A. By Lemma 7, we get a 4Ccompetitive algorithm A 2 for Online-Sorting[2C, n]. Theorem 1 implies that 8C 2 = Ω(log n/ log log n).

In particular, C = Ω( log n/ log log n).

Specifically, the proof of Theorem 1 yields a stream of n reals where A 2 incurs a cost of Ω( log n/ log log n). By the proof of Lemma 7, this translates to a stream of n parallelograms that can be packed in a strip of width 2, while A 1 produces a packing of width Ω( log n/ log log n).

We even get a non-constant asymptotic lower bound.

Corollary 13. For any algorithm A for Strip-Packing, a lower bound on the asymptotic competitive ratio of A is Ω( log n/ log log n), where n is the number of pieces, even when restricted to pieces of diameter less than 2.

Proof. Assume for contradiction that A has asymptotic competitive ratio g(n) = o( log n/ log log n). Let P(A) be the stream described in Corollary 12, where A produces a packing of width Ω( log n/ log log n), while the optimal packing has width at most 2.

There exists a function f such that: (i) f (n) · g(n) ≤ log n/ log log n, (ii) f (n) ≤ n 2 , (iii) f (n) = ω(1), and (iv) f is non-decreasing. If we append f (n) unit squares to the stream P(A), we obtain a stream Q(A) of n := n + f (n) ≤ 2n pieces. Taking Q(A) as input, A produces a packing of width Ω( log n/ log log n) while the optimum is Θ( f (n)). This implies that A has a competitive ratio of Ω log n/ log log n f (n)

= ω √ log n / log log n f (n ) on instances having arbitrary large (at least f (n)) optimal offline cost, contradiction.

The insights of Corollaries 12 and 13 imply negative answers also for various other online packing problems.

Theorem 2. The following holds, where n is the number of pieces:

(a) Strip-Packing does not allow for a competitive online algorithm, even if all pieces have diameter at most δ for any constant δ > 0. In particular, the competitive ratio of any algorithm is Ω( log n/ log log n).

(b) Bin-Packing does not allow for a competitive online algorithm, even if all pieces have diameter at most δ for any constant δ > 0. In particular, the competitive ratio of any algorithm is Ω( log n/ log log n).

(c) Perimeter-Packing does not allow for a competitive online algorithm, even if all pieces have diameter at most δ for any constant δ > 0. In particular, the competitive ratio of any algorithm is Ω( 4 log n/ log log n).

(d) Square-Packing[δ] does not allow for an online algorithm for any δ ∈ (0, 1]. In particular, for any algorithm and infinitely many n, there exists a stream of n pieces of total area O( log log n/ log n) that the algorithm cannot pack in the unit square.

Here, (a) and (b) even hold in the asymptotic sense, i.e., if we restrict ourselves to instances with offline optimal cost at least C, for any constant C > 0.

Proof. For each of the four packing problems, we consider an arbitrary algorithm A * , where A * packs pieces into a container S * . Here, S * may be a strip, a set of bins etc., depending on the problem at hand. The main idea in all the proofs is to cover S * by (rotated) substrips of a strip S of height 1/c for a (large) constant c, so that we get a correspondence between points in S * and S. By feeding A * with a stream of parallelograms and observing where they are placed in S * , we get an online algorithm A for packing (slightly modified) parallelograms into S. We can then by Corollary 13 choose a stream that forces A to produce a packing much larger than the optimal one, which implies that A * has likewise produced a bad packing. This gives a lower bound on the competitive ratio of A * . For a horizontal parallelogram P , a 2-extended copy is a parallelogram obtained by taking two copies of P and identifying the bottom base segment of one with the top segment of the other copy. We now prove each statement in the theorem.

(a) Suppose that A * is an algorithm for Strip-Packing restricted to pieces of diameter at most δ > 0.

The algorithm A * packs pieces into a strip S * of height 1. We define c := 4/δ . Recall that S is a strip of height 1/c. We cut S into substrips S 1 , S 2 , . . ., each of which is a rectangles of size 1 × 1/c. We rotate these by 90 • and use them to cover the strip S * . Let S * i be the part of S * corresponding to S i , so that the rectangles S * 1 , S * 2 , . . . appear in this order from left to right in S * ; see Figure 5 . We now define an algorithm A for strip packing horizontal parallelograms of height 1/c and diameter at most 2/c into S as follows. Let P be a piece to be packed in S, and let P * be the piece obtained from rotating the 2-extended copy of P by 90 • . Then P * has diameter at most 4/c = δ. We now feed P * to A * . We observe where A * places P * in S * . Since P * has width 2/c, it intersects both the left and right vertical edge of a substrip S * i . Then, in particular, P := P * ∩ S * i is congruent to P . We now place P in the substrip S i as specified by the placement of P in S * i . As A * does not place pieces in S * so that they overlap, this approach will produce a valid packing in S.

By Corollary 13, there exists for arbitrarily large n and α a stream I of n pieces of total area α where OPT(I) = O(α) whereas A(I) = Ω( log n/ log log n). Let I * be the stream of 2-extended pieces which we feed to A * . We then have OPT(I * ) = O(α), as we can just sort the pieces I * by the slope of their spine segments and place them in one long row in S * , which will form a packing of cost at most OPT(I) + 2/c = O(α). Since A(I) ≤ c · A * (I * ), we also have A * (I * ) = Ω( log n/ log log n). The statement then follows.

(b) The proof is almost identical to that of (a), so we only describe the parts that are different. Suppose that A * is an algorithm for Bin-Packing restricted to pieces of diameter at most δ > 0. Here, A * packs pieces into unit square bins B 1 , B 2 , . . ..

We again partition S into substrips and cover the boxes B 1 , B 2 , . . . with these, as shown in Figure 6 . We then get a strip packing algorithm A in S in a similar way as in (a), and obtain a lower bound on the asymptotic competitive ratio of A * in a similar way.

(c) Suppose there exists a C-competitive online algorithm A * for Perimeter-Packing. We prove that this implies the existence of an algorithm for Square-Packing[1/160C 2 ], and it follows from (d) that Figure 6 : The figure shows the correspondence between the bins B1, B2, . . . and S. C = Ω( 4 log n/ log log n). By Theorem 6 (c), every set of convex polygons of diameter at most 1/10 and total area at most 1/10 can be packed in a 1 × 1 square. Scaling by 1/4C, we get that convex polygons of diameter at most 1/40C and total area at most 1/160C 2 can be packed in a 1/4C × 1/4Csquare. In particular, the same holds if we bound the diameters to be at most 1/160C 2 . Hence, such a set of polygons can be packed in a box of perimeter 1/C. It follows that A * will produce a packing with a convex hull of perimeter at most 1. Therefore, the packing will be contained in the disk of radius 1/2 centered at any corner of the first piece P 1 , and in particular in the unit square centered at this corner. In other words, we have defined an algorithm for the problem Square-Packing[1/160C 2 ], and the claim follows.

(d) Consider an online algorithm A * for packing a stream of pieces of diameter at most δ ∈ (0, 1] into the unit square. For arbitrarily large values of n, we prove that there exists a stream of pieces of diameter at most δ and total area O( log log n/ log n) that A * cannot pack into the unit square. Let d > 0 be a lower bound on the multiplicative constant hidden in the first Ω-symbol of Corollary 13. We use the same setup as in (b), just with a single box B, which is covered by the c := 4 d 2 log n log log n first substrips of S. By Corollary 13, there exists a stream P 1 , . . . , P n of pieces such that A produces a packing of width 4 d 2 log n/ log log n, so that A * cannot fit the stream of 2-extended pieces in B. We may without loss of generality assume that n is sufficiently large that 4/c ≤ δ, so that the 2-extended pieces have diameter at most δ. The pieces have total area O(1/c 2 ) = O( log log n/ log n), and the statement follows.

You are asked to suggest an algorithm for online translational strip packing of convex pieces. What is the first approach that comes to your mind? It may very well be the following greedy algorithm: For each piece P i that appears, place P i as far left into the (horizontal) strip as possible. This algorithm is n-competitive: Indeed, it will occupy no more than n · max i width(P i ) of the strip, and the optimum must occupy at least max i width(P i ). This bound is unfortunately also essentially tight: Consider a sequence of very skinny pieces of height 1 and width 1, but with slopes alternating between 1 and −1. The algorithm will produce a packing of width n, while the optimum has width slightly more than 2 (depending on the actual fatness of the pieces).

We found it surprisingly difficult to develop an algorithm provably better than the naive algorithm, but in the following, we will describe an O(n log 3−1 log n)-competitive algorithm (note that log 3 − 1 < 0.59). We denote the algorithm OnlinePacker.

We first describe the algorithm and carry out the analysis when all the pieces are parallelograms of a restricted type and then show, in multiple steps, how the method generalizes to arbitrary convex pieces. By rescaling, we may without loss of generality assume that the first piece presented to the algorithm has width 1.

In the following we describe and analyze the algorithm OnlinePacker for online translational strip packing under the assumption that all pieces P are horizontal parallelograms where height(P ) = 1 and width(P ) ≤ 1.

We define an infinite family of box types as follows. The box types can be represented by an infinite ternary box type tree; see Figure 7 . The empty vector [ ] denotes the basic box type, which is simply a rectangle of size 2 × 1. Each box type will be defined as a horizontal parallelogram of height 1. Proof. We prove the lemma by induction on d. The claim clearly holds for d = 0, because the basic box type is a rectangle of size 2 × 1 and s has height 1 and width at most 1. Suppose that for some dimension d ≥ 0, there is a box type T that satisfies the lemma. We then partition the bottom and top edges of T , as described in the definition of the box types. We choose x d+1 ∈ {−1, 0, +1} such that t x d+1 contains the upper endpoint of s. Then T ⊕ [x d+1 ] is a (d + 1)-dimensional box type that satisfies the claim.

Lemma 15. For every horizontal parallelogram P where height(P ) = 1 and width(P ) ≤ 1, there exists a box type T such that P can be packed into T and area(T ) ≤ 6 area(P ).

Proof. Let be the length of the horizontal segments of P . Choose d ≥ 0 as large as possible such that 3 −d ≥ ; this is possible because ≤ 1. Let s be a segment of height 1 parallel to the non-horizontal edges of P and consider the d-dimensional box type that contains s as described in Lemma 14. If the top endpoint of s is in the right half of the top edge of T , then we place P to the left of s, i.e., with the right edge of P coincident with s. Otherwise, we place P to the right of s. Since the horizontal segments of T have length 2 · 3 −d ≥ 2 , it follows that T can contain P . Moreover, by maximality of d, the base edges have length less than 6 , so it follows that area(T ) ≤ 6 area(P ).

If a piece P can be packed into a box type T and area(T ) ≤ 6 area(P ), as in the lemma, then we say that T matches P . We say that a box type T is suitable for a piece P if T is an ancestor in the box type tree of a box type that matches P . In particular, P can be packed in a box B of a suitable type, but the area of B may be much more than 6 area(P ). We consider a type T to be an ancestor of itself.

Our algorithm will allocate space of the strip for boxes of the various box types. Each box of type T contains either:

• a piece P that T matches, or

• one, two, or three boxes of types that are children of T in the box type tree.

We now explain the behavior of our algorithm OnlinePacker when a new piece P arrives; see Figure 8 . Suppose first that there exists a box B 1 that satisfies the following properties. Figure 8 : An evolving packing produced by the algorithm. In each case, the green piece has just been placed. In the third step, there was no box suitable for the piece which also had room for it, so we allocated a new basic box.

• The type T 1 of B 1 is suitable for P , i.e., T 1 is an ancestor of a type T k that matches P in the box type tree. Here, T 1 , . . . , T k be the path from T 1 to T k in the box type tree.

• The box B 1 has room for one more box of type T 2 .

If more than one such box exist, we choose B 1 as small as possible, i.e., with maximum dimension. If B 1 exists, we do the following for each i = 1, . . . , k − 1: We allocate in B i an empty box B i+1 of type T i+1 which is placed in B i as far left as possible. At last, we place P in the box B k . Thus, each of the new boxes B 2 , . . . , B k−1 will contain a single box, and B k will contain P .

If such a box B 1 does not exist, we allocate a new box of the basic type and place it as far left in the strip as possible (that is, without overlapping with any already allocated box). We then define it to be our box B 1 and do as explained above; allocating a chain of nested boxes until we get to a type that matches P and place P there.

We say that a d-dimensional box is near-empty if there is exactly one (d + 1)-dimensional box allocated in it. A crucial property of OnlinePacker is that it does not produce an excessive number of near-empty boxes, as described in the following lemma. Lemma 16. There can be at most two near-empty boxes of each type in a packing produced by OnlinePacker.

Proof. Suppose that there are two near-empty boxes B 1 and B 2 of type T , where B 1 was created first. Let P be the piece that caused B 2 to be allocated. We first see that one of the two boxes, say B 1 , must contain a box B 1 of type T ⊕ [−1] and the other, B 2 , must contain a box B 2 of type T ⊕ [+1]: If B 1 and B 2 had the same type or one of them had type T ⊕ [+0], then they could be packed in the same box of type T ; see Figure 9 . Hence, P could have been placed in B 1 instead of allocating the new box B 2 , contradicting that we allocate new boxes in a smallest possible existing box.

But since B 1 has type T ⊕ [−1] and B 2 has type T ⊕ [+1], it follows that the next box of type T ⊕ [x], for x ∈ {−1, 0, +1}, can be placed in B 1 or B 2 . Therefore, the algorithm will never allocate a third near-empty box of type T .

We will now analyze the density under the assumption that there are no near-empty boxes. We shall then reduce the general case to this restricted case.

Lemma 17. Suppose that OnlinePacker has produced a packing of n horizontal parallelograms of height 1 and width at most 1, where there are no near-empty boxes. Then the density of the pieces in the occupied part of the strip is at least Ω(n 1−log 3 ).

Proof. We prove that when there are no near-empty boxes, then the density in each basic box is at least n 1−log 3 , and the lemma follows. So consider a basic box B and let n B be the number of pieces packed in B. The box B and the boxes allocated in it can be represented as a rooted tree T 1 . Here, the root is B and the children of a d-dimensional box are the (d + 1)-dimensional boxes that it contains, and each leaf is a box that contains a piece. Since there are no near-empty boxes, each internal node in T 1 has two or three children. To get a lower bound on the density in B, we construct a sequence of trees T 1 , T 2 , . . . , T k , where each tree corresponds to a packing in a basic box. The density of these packings decreases, and we will see in the end that the density in T k is at least Ω(n 1−log 3 ).

The final tree T k is balanced in the sense that all leaves are contained in two neighbouring levels d and d + 1. If a tree T i is not balanced, we construct T i+1 in the following way. Let d be the maximum dimension of a box in T i . We can find two or three leaves of dimension d u that have the same parent u. If there are three, we remove one of them and the unique piece it contains from the packing, which decreases the density, and then proceed as in the case where there are two, as described in the following. Let u 1 , u 2 be the two leaves. Suppose that there is also a leaf v at level d v ≤ d u − 2. Recall that a d-dimensional box has area 2 · 3 −d . Thus, the area of pieces in the boxes u 1 , u 2 , v combined is at least

We now make a replacement argument: We "move" the leafs u 1 , u 2 , so that they become children of v instead of u, and argue that this only decreases the density. So, we construct a tree T i+1 that is similar to T i , except u is now a leaf and v has two children v 1 , v 2 . For this to be a conceivable packing, we must remove the pieces that were before in u 1 , u 2 , v and place new pieces in u, v 1 , v 2 . We place pieces in u, v 1 , v 2 that fills the boxes with density 1/6. These new pieces have total area

It is now straightforward to verify that since d v + 2 ≤ d u , we have A ≤ A. Hence, the density in T i+1 is smaller than the density in T i .

In the end, we obtain the packing represented by a balanced tree T k , where all leaves are d-or (d + 1)dimensional for some value d ≥ 0. We then have d ≤ log n B + 1. Therefore, each piece has area at least 2 · 3 − log n B −1 /6 = Ω(3 − log n ), and the total area of the pieces is Ω(3 − log n B · n B ) = Ω(n 1−log 3 B ) = Ω(n 1−log 3 ), which is also a lower bound on the density.

We now prove that when the total area of pieces is at least 1, then the density of an arbitrary packing produced by the algorithm, i.e., where there may also be near-empty boxes, is not much smaller.

Lemma 18. Suppose that OnlinePacker has packed n horizontal parallelograms of height 1 and width at most 1. If the total area of the pieces is at least 1, the resulting packing has density Ω(n 1−log 3 / log n).

Proof. Let A be the area of the strip used by the algorithm, and let Σ be the total area of the pieces. We show that by replacing some boxes and pieces, so that the total area of pieces increases by at most F = O(log n), we obtain a packing with m pieces, where m ≤ n, and no near-empty boxes. We then get from Lemma 17 that the resulting packing has density

Using that Σ ≥ 1, it then follows that the original density is

= Ω(n 1−log 3 / log n).

Consider a maximal near-empty box B 1 , i.e., a near-empty box that is not contained in a larger nearempty box. We remove all boxes contained in B 1 and the pieces they contain and instead place a single piece in B 1 that completely fills B 1 . This operation cannot increase the number of pieces, because there was at least one piece contained in B 1 before.

Let d be maximum such that there are at least 2 d near-empty d-dimensional boxes. We first observe that d ≤ log n: Each of the near-empty d-dimensional boxes contains a distinct piece. We therefore have 2 d ≤ n, so that d ≤ log n.

Let F ≤d be the total area of pieces that we add to eliminate maximal near-empty boxes of dimension at most d and let F >d be the remaining ones, so that F = F ≤d + F >d .

In order to bound F ≤d , we note that there are 3 i types of i-dimensional boxes, each of which has area O(3 −i ). For each maximal near-empty i-dimensional box, we add a piece of area O(3 −i ). As there are at most two near-empty boxes of each type by Lemma 16, we add boxes of total area O(

By similar arguments, we get

so we conclude that F = O(log n), which finishes the proof.

We now describe an extension of OnlinePacker in order to handle horizontal parallelograms of arbitrary height (at most 1) and bounded extended width, to be defined shortly. Here, we partition the pieces into height classes, so that a piece P belongs to class h if 2 −h−1 < height(P ) ≤ 2 −h . For height class h, the base type is a rectangle of size 2 × 2 −h , and in the strip we allocate boxes of this size in which to pack pieces from the height class. We define an infinite ternary box type tree for each height class, exactly as when all the pieces have height 1. When a piece P arrives, we determine the height class h of P . We extend the non-horizontal segments of P until we obtain a horizontal parallelogram of height exactly 2 −h , and we denote the resulting piece P so that P ⊂ P . We then define the extended width of P as extwidth(P ) := width(P ). Note that since 2 −h−1 < height(P ), we have height(P ) < 2 height(P ) and extwidth(P ) = width(P ) < 2 width(P ). We then pack P (including P ) into a minimum suitable box that has already been allocated, if possible, and otherwise allocate a new basic box.

We stack the basic boxes of different height classes if possible. When a new basic box of height class h is created, we stack it on the leftmost pile of basic boxes that has room for it. This choice implies that there can be at most one stack of basic boxes that is less than half full.

Lemma 19. Suppose that OnlinePacker has packed n horizontal parallelograms of width at most 1/2 and total area more than 2. The resulting packing has density Ω(n 1−log 3 / log n).

Proof. Let U be the union of the base boxes (across all height classes), and let A be the area of the part of the strip occupied by the packing. Since the total area of pieces is more than 2, we also have area(U ) ≥ 2. Suppose first it holds that the density in U is at least Ω(n 1−log 3 / log n). We have that area(A) ≤ 2 area(U )+2, since there is at most one stack of base boxes of height less than 1/2 in the packing. Since 2 < U , we then also have area(A) < 3 area(U ). We can therefore also conclude that the density of the occupied part of the strip is Ω(n 1−log 3 / log n).

We now prove the density bound in U . Let Σ be the total area of the pieces. For each height class h for which there are some pieces, we feed the algorithm with a rectangle of size 1 × 2 −h . Let F be the total area of these pieces, and we have F < ∞ h=0 2 −h = 2. We therefore have 2Σ ≥ Σ + F . Let U be the union of the base boxes in this expanded packing. We then have that the original density is

.

Since the area of pieces in each non-empty height class h is at least 2 −h , we can now apply Lemma 18 (by scaling the y-coordinates by a factor of 2, we obtain a packing of parallelograms of height 1). Let n h be the number of pieces in height class h. We get that the density in the base boxes of height 2 −h is Ω(n 1−log 3 h / log n h ) = Ω(n 1−log 3 / log n), so this is a bound on the density in all of U . Hence we have Σ area U = Ω(n 1−log 3 / log n), and this concludes the proof.

We now describe an extension of OnlinePacker that handles horizontal parallelograms of arbitrary height and arbitrary width. We partition the parallelograms into width classes. Pieces of width class i are packed in base boxes of width 2 i . Consider a parallelogram P . If extwidth(P ) ≤ 1, then the width class of P is i = 1. Otherwise, P belongs to the width class i such that 2 i−1 < 2 extwidth(P ) ≤ 2 i . We handle each width class independently, so that pieces from each class are packed in stacks as described in Section 5.2.2. In particular, each width class i is subdivided into height classes, and we allocate in the strip rectangles of size 2 i × 1, where we can place a stack of base boxes of sizes 2 i × 2 −h , for various values of h ≥ 0.

When a new piece P arrives, we determine its width class w and height class h. Then, we pack it into a rectangle of size 2 w × 1, in a base box of size 2 w × 2 −h that has room for it. If no rectangle of that size has room for P , a new rectangle of size 2 w × 1 is created and placed as far left in the strip as possible.

Lemma 20. The competitive ratio of OnlinePacker when applied to n horizontal parallelograms of arbitrary width is O(n log 3−1 log n).

Proof. After OnlinePacker has packed the n parallelograms, we denote the cost of the produced solution as ALG and the optimal offline solution as OPT. We then feed the algorithm with four rectangles of size 2 i−2 × 1 for each width class i for which there are some pieces. We denote the cost of the resulting packing as ALG + and the cost of the optimal offline solution as OPT + . Suppose that the largest width class is class k. We now claim that some piece P has extended width more than 2 k−2 . If k > 1 this holds for any piece in width class k, and if k = 1, it follows since we assume that the first piece presented to the algorithm has width 1. We then have OPT ≥ width(P ) > extwidth(P )/2 > 2 k−3 . Since the added pieces are rectangles of height 1, the optimal packing is similar to the optimal packing for the original instance with the extra pieces added in the end. We therefore have

Let n i and Σ i be the number and total area of the pieces in width class i, respectively. Note that Σ i > 2 i , so that we can apply Lemma 19 to each width class (under proper scaling). The bound on the competitive ratio becomes

17n log 3−1 log n · Σ Σ = O(n log 3−1 log n).

We now describe the extension of OnlinePacker to handle arbitrary convex pieces; see Figure 10 . When a new piece P arrives, we find a horizontal parallelogram P such that P ⊂ P , area(P ) ≤ 2 area(P ) and width(P ) ≤ 2 width(P ); then we apply OnlinePacker to the parallelogram P (with P inside). We define P as follows. Let b and t be the lower and upper horizontal tangent to P , respectively, and let c b ∈ P ∩ b and c t ∈ P ∩ t . Let l and r be the left and right tangent to P parallel to the segment c b c t , respectively. We then define P to be the horizontal parallelogram enclosed by the lines b , t l , r .

It is straightforward to check that area(P ) ≤ 2 area(P ), because P is convex. Now we prove that width(P ) ≤ 2 width(P ). Define L to be the length of the horizontal edges of P and note that width(P ) = width(c b c t ) + L. On the other hand, width(P ) ≥ max{width(c b c t ), L}, and this proves the claim.

In the proof of Lemma 20 we only bound OPT using the width of the widest piece and the total area Σ. With respect to both width and area, the value for an arbitrary convex pieces P is at least 1/2 of that of the containing parallelogram P . Therefore, the bound on the competitive ratio carries over up to constant factors when the algorithm is applied to the parallelograms P , as stated in the following. Proof. Alt, de Berg, and Knauer [5, 6] presented an algorithm that packs any set P of convex polygons (with n vertices in total, using O(n log n) time) into an axis-aligned rectangular container B such that area(B) ≤ 23.78 · opt, where opt is the minimum area of any axis-aligned rectangular container for P. As an intermediate step, they obtain a collection of rectangular mini-containers that together contain all objects of P. Let w max and h max denote the maximum width and height among all objects of P, respectively. For some fixed constants c > 0, α ∈ (0, 1), each mini-container has width (c + 1)w max and a height h i where h i := α i h max for some appropriate i. The total area A C of all mini-containers can be bounded by

In order to prove (a), (b), (c), and (d), we repeatedly make use of the mini-containers and this equation.

We first consider strip packing and prove (a). When packing a set of convex polygons P into a horizontal strip of height 1, the minimal width opt-w is at least max{w max , area(P)}. Therefore,

We group the mini-containers greedily into stacks of height at most 1, which we place in the strip. Note that all but possibly one stack have a height of at least 1 /2; otherwise two of these should have been put together. Therefore, the number of stacks is at most 2A C (c+1)wmax + 1. Together with α := 0.545 and c := 2.2, this translates into a width of 2A C + (c + 1)w max ≤ 2 · (1 + 1 /c) · 2 α + c + 2 /α 1 − α + c + 1 · opt-w < 32.7 · opt-w.

We now turn our attention to (d), and our findings will later be used to prove (b). Let S denote the unit square in which we want to pack a given set P of convex polygons, each of diameter at most δ. We choose α := 1/2 and choose the width of the mini-containers to be 1, i.e., (c + 1)w max = 1. 2 We stack all mini-containers on top of each other. Suppose that the total height of the mini-containers exceeds 1. We prove that the total area of pieces is then more than the constant ρ := (1 − 5δ)(1 − 2δ)/4. For δ := 1/10, we get ρ := 1/10, and the claim in the theorem follows.

We call a mini-container full if the bounding box of all contained pieces has width more than 1 − δ; otherwise there is room for a further piece. A mini-container that is not full is called near-empty. We can pack the pieces such that in each height class, there is at most one near-empty mini-container. Therefore, the total height of near-empty mini-containers is at most i h i = h max i α i ≤ δ/(1 − α) = 2δ. Since the mini-containers (full and near-empty) have a total height of more than 1, the full mini-containers in S have a total height of more than 1 − 2δ, and a total area of more than 1 − 2δ.

Let B be the bounding box of a full mini-container of height h i (and area h i ) and denote the set of contained polygons by P . By [5, 6] , we obtain (1 − δ)h i ≤ area(B) ≤ 2/α · area(P ) + h i w max ≤ 4 area(P ) + h i δ .

Consequently, area(P ) ≥ (1 − 5δ)h i /4 and thus the density in any full mini-container is at least (1 − 5δ)/4. As the total area of the full mini-containers in S is more than 1 − 2δ, the total area packed into S is more than ρ := (1 − 5δ)(1 − 2δ)/4.

We use the described algorithm for square packing to prove statement (b). By the above strategy, if area(P) ≤ 1/ρ, where ρ := (1 − 5δ)(1 − 2δ)/4, then the algorithm will use only one bin, so the packing achieves the optimum in this case. We may therefore assume area(P) > 1/ρ. We can guarantee a density of at least ρ in all but one bin. Consequently, the number of bins is at most area(P)/ρ + 1. Clearly, the number of bins in the optimal solution is at least area(P). Therefore, the approximation ratio is at most area(P)/ρ + 1 area(P) ≤ 1/ρ + ρ.

Using δ := 1/10 yields the ratio 10.1 as stated in the theorem. We finally prove (c). In order to obtain a bounding box with small perimeter, we consider the minicontainers in a greedy fashion (from largest to smallest height) and pack them on top of each other into stacks of height at most H := √ A C + h max and width (c + 1)w max . Clearly the height of each stack except possibly the last one is at least √ A C . Consequently, the number of stacks is at most √ A C (c+1)wmax + 1. Hence, we obtain a bounding box with perimeter of at most 4 √ A C + 2h max + 2(c + 1)w max . Because the optimal perimeter opt-p is at least max{2w max + 2h max , 4 area(P)}, we have h max w max ≤ opt-p 2 /8 and area(P) ≤ opt-p 2 /16. We then get from Equation (1) that

Finally, choosing α := 0.5 and c := 1.06, we obtain 4 A C + 2h max + 2(c + 1)w max ≤ 4 (1 + 1 /c) · 2 α · 1 16 + c + 2 /α 1 − α · 1 8 + 1 + c · opt-p < 8.9 · opt-p.

This completes the proof. 2 In fact, we can choose α depending on δ to get a denser packing. It turns out that α := 1 − √ 3δ 3 −4δ 2 +δ 1−δ is the optimal value, but we stick to α := 1/2 to keep the analysis simpler.

Online Packing to Minimize Area or Perimeter

Aligning two convex figures to minimize area or perimeter

Online scheduling

Computational Aspects of Packing Problems

Approximating minimum-area rectangular and convex containers for packing convex polygons

Corrigendum to: Approximating minimum-area rectangular and convex containers for packing convex polygons

Packing 2D Disks into a 3D Container

Packing Convex Polygons into Rectangular Boxes

Shelf algorithms for two-dimensional packing problems

Tight Bounds for Online TSP on the Line

Improved Bound for Online Square-into-Square Packing

A Review of Machine Scheduling: Complexity, Algorithms and Approximability

Approximation and online algorithms for multidimensional bin packing: A survey

Efficient packings of unit squares in a large square

On-line packing and covering problems

Shelf Algorithms for On-Line Strip Packing

Multidimensional packing problems

On packing squares with equal squares

Online Square-into-Square Packing

Competitive analysis of algorithms

On-line scheduling on a single machine: Minimizing the total completion time

Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

A new upper bound 2.5545 on 2D Online Bin Packing

Strip Packing vs. Bin Packing

Online removable square packing

On-line packing sequences of cubes in the unit cube

A proof of an Auerbach-Banach-Mazur-Ulam theorem on convex bodies

An on-line potato-sack theorem

Determining in Linear Time the Minimum Area Convex Hull of Two Polygons

Dense packings of congruent circles in rectangles with a variable aspect ratio

Minimum perimeter rectangles that enclose congruent non-overlapping circles

The Scottish Book: Mathematics from the Scottish Café, with Selected Problems from the New Scottish Book

Rotational polygon containment and minimum enclosure using only robust 2D constructions

Translational polygon containment and minimal enclosure using linear programming based restriction

Translational polygon containment and minimal enclosure using mathematical programming

Some packing and covering theorems

Bundling three convex polygons to minimize area or perimeter

Online scheduling

On-line scheduling

High density packings of equal circles in rectangles with variable aspect ratio

SIGACT news online algorithms column 20: the power of harmony

SIGACT News Online Algorithms Column 26: Bin packing in multiple dimensions

A note on online strip packing

We thank Shyam Narayanan for improving the upper bound algorithm in Theorem 3 to the asymptotically tight upper bound of O( √ n). We highly appreciate the BARC espresso machine, the comfy couches in the Creative Room, and the cucumbers. We also thank Linda's travel grant, Denmark for opening the borders in the right moment after a COVID-19 lockdown, and the lenient train officer who trusted the great authority of Mikkel's letter of invitation, allowing for travelling to Copenhagen and making this work possible.