On geometric properties of enumerations of axis-parallel rectangles

On Geometric Properties of Enumerations of Axis-Parallel Rectangles 1 Kira Vyatkina Research Institute for Mathematics and Mechanics, St Petersburg State University, 28 Universitetsky pr., Stary Peterhof, 198504, St Petersburg, Russia Abstract We show that for any set of non-overlapping axis-parallel rectangles in the plane, there exists a sloping enumeration, such that the numbers of rectangles intersected by any line with a non-negative slope increase along this line. Such enumeration can be computed in the optimal time Θ(nlog n) using linear space. The notion of a sloping enumeration can be generalized to higher dimensions; however, already in three-dimensional space it may not exist. We also consider a strip packing problem for a set of rectangles with a fixed enumeration, which is required to be sloping for the resulting packing. This problem is proved to be NP-hard in any dimension d≥2. Key words: rectangles, enumeration, orthogonal packing, NP-hardness 1. Introduction AYoung diagram is a collection of boxes, arranged in left-justified rows, with a (weakly) decrasing number of boxes in each row (Fig. 1a). A standard Young tableau is obtained by placing the numbers 1, 2, . . . , nin the nboxes of the diagram in such way that the numbers increase across each row and down each colomn (Fig. 1b). a) b) 1 3 7 10 12 2 5 9 4 8 6 11 Fig. 1. a) A Young diagram; b) a standard Young tableau. Young diagrams were introduced by Alfred Young in 1900 as a combinatorial tool (see [9]); Email address: [email protected] (Kira Vyatkina). 1This work is partially supported by Russian Foundation for Basic Research (grant 04-01-00173). at present combinatorics of Young tableaux has a wide range of applications in algebraic geometry and representation theory (see for example [6]). Sometimes Young diagrams are written upside down (Fig. 2a). Instead of considering a Young tableau as a combinatorial structure, let us look at its geometric representation: consider a standard Young tableau written upside down as a set of enumerated unit squares drawn in the plane, touching their boundaries. It is easy to see that for any line lwith a nonnegative slope, the numbers of squares intersected by lincrease along l(Fig. 2a). We generalize this observation in the following way: for any set of non-overlapping axis-parallel rectangles in the plane, there exists a sloping enumeration, such that for any line lwith a nonnegative slope, the numbers of rectangles intersected by lincrease along l(Fig. 2b). Such enumeration can be efficiently computed in Θ(nlog n) time and O(n) space. These results can be viewed as a new interpretation of our recent results [3]. All standard Young tableaux corresponding to a given Young diagram can be obtained as a topological ordering of vertices of a particular graph associated with the diagram (see [9]). All sloping enumerations for a set Rof rectangles can be ob- 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry a) 1 3 7 10 12 2 5 9 4 8 6 11 b) 4 1 3 2 5 6 7 l1l2 Fig. 2. a) A Young tableau written upside down; line l1con- sequently intersects squares 1, 2, 4, 6, 11. b) An enumerated set of rectangles; line l2consequently intersects rectangles 1, 3, 5, 6. For both a) and b), numbers of squares/rectangles intersected by any line with a non-negative slope increase along this line. tained in the same way from a placement graph associated with R. It is straightforward to generalize the notion of a sloping enumeration to higher dimensions; however, we provide an example showing that even in three-dimensional space, a sloping enumeration may not exist. Astrip packing problem is a special type of orthogonal packing problems (see the classification schemes introduced in [5,11]); much research has been recently carried out on problems of this kind (see the references in [5]). We consider the strip packing problem in the following form: given a set of enumerated rectangles and a horizontal strip of height H, we have to pack all rectangles into the strip, in such way that the given enumeration would be sloping for the resulting packing. As a matter of fact, we usually follow these restrictions when packing our luggage – since, for example, we do not want heavy objects to press down fragile ones. Asking for the minimal length of the strip, sufficient to store all rectangles, is shown to be NP- hard. This result can be generalized to an arbitrary dimension. 2. Preliminaries Further we shall assume that all rectangles are axis-parallel, and no two of them overlap. We borrow terminology from [1,2,4]. For a rectangle p, let us denote its lower left, upper left, upper right and lower right vertices by Ap, Bp,Cp, and Dp, respectively. A zone Z(p) of rectangle pis an open lower left quadrant built from point Cp(Fig. 3a). Given a set Rof rectangles, its placement graph GRhas a vertex for each rectangle p∈R; for two vertices pand q,GRcontains an arc (p, q) iff p∩Z(q)6=∅(Fig. 3b). Z(p) p Dp Cp Bp Ap a) b) Fig. 3. a) Rectangle pand its zone Z(p); b) a set of rectangles and the corresponding placement graph. The following properties were observed in [2,10]: Lemma 1 Let p, q ∈R. If p∩Z(q)6=∅, then q∩Z(p) = ∅. Theorem 2 GRis acyclic. 3. Sloping Enumerations Theorem 2 implies that the vertices of GRcan be topologically sorted; it follows (see [2,10,1]) that: Theorem 3 For any set R, there exists an enumeration IR:R↔ {1,2,...,N}, where N=|R|, such that ∀p∈R:∪{Z(q)|IR(q)< IR(p)} ∩ p=∅. It is easy to prove that enumeration IPsatisfies our requirements. Theorem 4 IRis sloping. PROOF. Consider a line lwith a non-negative slope; let us assume that lintersects at least two rectangles. Denote the intersected rectangles by pk1,...,pkm, according to the order, in which they are intersected by l(Fig. 4). pk1 pk2 pkm l Fig. 4. Line lconsequently intersects rectangles pk1,pk2, . . . , pkm. For 1 ≤i < j ≤m, we have pki∩Z(pkj)6=∅. March 25-26, 2004 Seville (Spain) Obviously, 1 ≤i < j ≤mimplies pki∩Z(pkj)6= ∅, and thus, IR(pki)< IR(pkj) must hold. It can be easily proved by induction that IR(pk1)<···< IR(pkh) for any 1 ≤h≤m; this completes our proof. A sloping enumeration need not be unique. To build some sloping enumeration, one may construct the placement graph GRand sort topologically its vertices. Graph GRcan be constructed with a plane sweep algorithm in O(nlog n+|ER|) time and O(n) space, where |ER|is the number of its edges. This algorithm is optimal in the comparison tree model. The sorting can then be performed in O(n+|ER|) time; thus, computing a sloping enumeration in this way would take us O(nlog n+|ER|) time. The method described above is not optimal; however, a sloping enumeration can be obtained in the optimal Θ(nlog n) time and in linear space using a plane sweep algorithm; the reader is referred to [3] for details. 4. Strip Packing Problem Let us consider a two-dimensional strip packing problem with respect to a given enumeration (SPPE-2). The optimization problem is: SPPE-2: Given a set of enumerated rectangles and a horizontal strip of height H, we ask for the minimal length Lof the strip, sufficient to pack all rectangles in such way that the given enumeration is sloping for the resulting packing. The corresponding decision problem is: SPPE-2*: For a given a set of enumerated rectangles and a horizontal strip of height Hand length L, is there a feasible packing, for which the given enumeration is sloping? Theorem 5 SPPE-2 is NP-hard. PROOF. Clearly, SPPE-2*∈NP. Let us reduce to SPPE-2* the PARTITION problem, which is known to be NP-complete [8,7]. In PARTITION, we are given a finite set Aand a size s(A)∈Z+ for each a∈A, and we ask if there exists a subset A′⊆A, such that Pa∈A′s(a) = Pa∈A\A′s(a). For set A={ai}n i=1, let H= 5, and L= 2Pn i=1 s(ai). For each ai∈A, we construct rectangle r(ai) of size 2s(ai)×2. In addition, we construct two rectangles r0and rn+1, each of size Pn i=1 s(ai)×2. We enumerate rectangles as follows: IR(r0) = 1, IR(rn+1) = n+ 2, IR(r(ai)) = i+ 1, for 1 ≤i≤n. Obviously, the length of the strip needed to pack all rectangles is at least L. It is precisely Liff the answer for the PARTITION decision problem is “yes”. 1 6 3 5 4 2 Fig. 5. Fig. 5 illustrates the reduction described above for set A={a1, a2, a3, a4}, with sizes s(a1) = 2, s(a2) = 1, s(a3) = 3, s(a4) = 2. Thus, L= 16; H= 5. Choosing A′={a1, a4}gives us a partition, and the packing shown on Fig. 5 fits into a strip of size H×L. Clearly, our enumeration is sloping for this packing. 5. Higher-Dimensional Case The notion of a sloping enumeration can be easily generalized to higher dimensions. In ddimensional space, we shall consider d-dimensional boxes instead of rectangles. Let us consider a set of vectors V={v|v= Pd i=1 aiei, ai≥0,1≤i≤d}, where eiare unit vectors pointing along coordinate axes. Enumeration IRof a set Rof boxes is sloping, if for any line l, such that ∃v∈V:l||v, the numbers of boxes intersected by lincrease along l. For d= 2, this definition is equivalent to the one given before. In the three-dimensional case, a sloping enumeration may not exist. A construction from [2], shown on Fig. 6, illustrates such situation. Notice that if we set in the definition a1≤0, a2, a3≥0, there will be a sloping enumeration. However, in [3] we introduce a construction, for which no sloping enumeration exists for any choice of signs for a1,a2, 20th European Workshop on Computational Geometry a3. (In [3], it serves as an example of a set of parallelepipeds admitting no right-angled cut partition.) . p q x y z s Fig. 6. For the set {p, q, s}, there exists no sloping enumeration. However, there will be a sloping enumeration, if we set a1≤0, a2, a3≥0: IR(q) = 1, IR(s) = 2, IR(p) = 3. Let us generalize to higher dimensions the strip packing problem. SPPE-d:Given a set of enumerated boxes in ddimensional space, we ask for the minimal length W1of a container, sufficient to pack all boxes in such way that the given enumeration is sloping for the resulting packing, where the sizes in the other d−1 dimensions W2, . . . , Wdare fixed. SPPE-d*: For a given a set of enumerated boxes in d-dimensional space and a container of size Wd, is there a feasible packing, for which the given enumeration is sloping? Theorem 6 SPPE-dis NP-hard. To prove this theorem, we apply reduction similar to the one described above, setting W2= 5, W3=··· =Wd= 1, and requiring box r(ai) to have size 2s(ai)×2×1· · ·×1, 1 ≤i≤n, and boxes r0and rn+1 – to have size Pn i=1 s(ai)×2×1· · ·×1. 6. Conclusion For an arbitrary set of non-overlapping axisparallel rectangles in the plane, we have proved existence of a sloping enumeration, and proposed methods for computing it efficiently. We have also considered a strip packing problem for an enumerated set of rectangles; an additional requirement concerned with the enumeration is the following: the given enumeration must be sloping for the resulting packing. This problem is shown to be NP-hard. We have generalized the notion of a sloping enumeration to the case of d-dimensional space. For the three-dimensional case, we gave an example of a set of parallelepipeds, which admits no sloping enumeration. However, the strip packing problem may be stated for any dimension d; we have proved it to be NP-hard in arbitrary dimension. All valid enumerations arise as a topological ordering of vertices of a placement graph. This graph is known to be acyclic [2,10]; however, we suppose that much more could be derived on its structure. We are going to consider this question, along with the opposite one: what kind of dags can appear as placement graphs? References [1] V. Bukhvalova, and L. Faina, Rectangular Cutting Layout Problem, http://loris.dipmat.unipg.it/usa/index.html. (1998). [2] V. Bukhvalova, Rectangular Cutting Problem: Zone Method and Other Algorithms (Saint Petersburg State Univ. Press, St Petersburg, 2001). (in Russian) [3] V. Bukhvalova, and K. Vyatkina, An Optimal Algorithm for Partitioning a Set of Axis-Parallel Rectangles with Right-Angled Cuts, in: M. Neamtu and M. Lucian, eds., Proceedings SIAM Conference on Geometric Design and Computing (Seattle, USA, 2003). (to be submitted) [4] L. Faina, An application of simulated annealing to the cutting stock problem, European Journal on Operational Research,114(3) (1999) 542–556. [5] S. Fekete, and J. Schepers, A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing, http://arxiv.org/abs/cs.DS/0310032. (2003). [6] W. Fulton, Young Tableaux with Applications to Representation Theory and Geometry (New York: Cambridge University Press, 1997). [7] M.R. Garey, and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP- completeness (San Francisco: Freeman, 1979). [8] R.M. Karp, Reductibility among combinatorial problems, in: R.E. Miller and J.W. Thatcher, eds., Complexity of Computer Computations (Plenum Press, New York, 1972) 85–103. [9] D. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition (Reading, Massachusetts: Addison-Wesley, 1998). [10] A.I. Lipovetsky, Properties of Rectangular Packings, manuscript (1988). (in Russian) [11] M. Wottawa, Struktur und algorithmische Behandlung von praxisorientiren dreidimensionalen Packungsproblemen (Ph.D. thesis, Universit¨at zu K¨oln, 1996).