Determining in Linear Time the Minimal Area Convex Hull of Two Convex Polygons Under Translation Hyun-Chan Lee Tony C. Woo The University of Michigan Department of Industrial & Operations Engineering Ann Arbor, Michigan 48109 Technical Report 86-35 September ]986

Determining in Linear Time the Minimal Area Convex Hull of Two Convex Polygons Under Translation Hyun-Chan Lee Tony C. Woo The University of Michigan Department of Industrial & Operations Engineering Ann Arbor, Michigan 48109 September 1986

<Abbreviated Title> Minimal Convex Hull of Two Convex Polygons <Mailing Address> Tony C. Woo Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 ii

Abstract Given two non-overlapping convex polygons P and Q, we find their relative positions such that the convex hull encasing them is minimal in area. Without loss of generality, we allow Q to translate about a fixed P. Let N be the total number of vertices in P and Q. We determine the minimal area convex hull in O(N) time. Instead of computing the convex hull after every translation, we compute the slope of a function for the added area and update it in constant time. We show that the added area function is piecewise linear and that there are only O(N) points on the curve where updating is necessary. Key Words Convex hull, Computational geometry, Minimum area, Algorithms. AMS Subject Classifications 52A15 Convex sets in 2 dimensions 52A45 Packing, covering, tiling (05B40) iii

List of Symbols AAF: Added area function. A:Added area of the current configuration. C Cb: Sum of constants corresponding to the base edges in the slope formula of AAF. CHV: Convex hull vertex. {CHV}: Set of CHV. C: Sum of constants corresponding to the current contact edge in the slope formula of AAF. e:Current contact edge. C e.: Initial contact edge. mA Minimal added area. C me e when the added area is minimal. c c mv: v when the added area is minimal. C C mt: t when the added area is minimal. c C n:Total number of vertices of polygon P. N: Total number of vertices of polygons P and Q. nt: Next refraction point in {t }. xc xc P, Q Convex polygons. S.: Slope of the edge vivi+. S Slope of the contact edge ec (vav ). tc: X component of the translated distance along ec from the vertex vp to the current refraction point. t (ty): X(Y) component of the translated distance along ec from xy~~~~~~~~~~~~~ iv

the current refraction point. t: X component of the translated distance along e from the xc c current refraction point to the next refraction point due to a change in the convex hull vertex. {t}: Set of t. xc xc tx: X component of the translated distance along e from the current refraction point to the vertex v v. it vertex of P and Q for i=1,2,....,N. 1 v (v ): Convex hull vertex belonging to P(Q) in the front added pa qa polygon. v (v q): Convex hull vertex belonging to P(Q) in the rear added polygon. vp (vqc): Current vertex of P(Q). pc qc vr (vqr): Initial touching vertex in P(Q). v (v): Vertex of the contact edge ec in the front (rear) added polygon. v: Current contact vertex. c Xi(Y): X or Y coordinates of v.. v

1. Introduction In computer science and operations research, allocating finite resources has been an important problem. This problem has many applications in industry and is characterized by the clustering of demands to minimize waste (or to maximize utility). The geometric problem of packing rectangular shapes is formulated as the Bin-Packing problem [6] and the Cutting-Stock problem [4]. It is NP-hard to determine optimal packing for rectangular shapes for which recent solutions have employed heuristics [2,7]. For non-rectangular shapes, it is reasonable to expect even greater difficulties. One approach to simplify the packing of non-rectangular shapes is to preprocess them by circumscribing with rectangles [1] and to pack the resulting rectangles [3]. Since rectangular circumscription produces more waste than convex circumscription, we develop a more space-efficient preprocessing algorithm by clustering the original shapes by two - specifically, two convex polygons into one with minimal convex hull. If a polygon is nonconvex, we can apply a linear time algorithm to find its convex hull [5]. Given two convex polygons P and Q, we assume that Q is allowed to translate along the boundary of P as shown by the sequence in Figure 1. Suppose the minimum area convex hull occurs at a configuration in which a vertex from P touches a vertex from Q. There are O(N) such possible configurations, where N is the total number of vertices of P and Q. For each such configuration, their convex hull can be found in O(N) time. Hence, brute force leads to an algorithm that would run in at least O(N ) time. But, such an algorithm is not guaranteed to work. As shown

in Figure l(c), the minimum area convex hull occurs in a configuration other than the discrete vertex-vertex configuration. <Insert Figure 1> Instead of calculating the total area of the convex hull of two convex polygons, we find an added area due to the convex hull since the area of two given polygons is constant. We show that an added area function is piecewise linear. Exploiting its piecewise linearity, we find the minimal added area configuration by calculating at points where the slope of the added area function changes. We call these points refraction points. To calculate the added area at refraction points, we triangulate the added area once at the initial configuration and update the slope of the added area function by calculating the amount of translation and the change in the triangle area to reach the next refraction point. Since the triangulation is done once in linear time and the updating at each refraction points is done in constant time, we find the minimal area configuration in O(N) time by showing the total number of refraction points to be O(N). This paper is organized as follows. In section 2, definitions and notations are given. In section 3, the added area function is examined. In section 4, initialization processes are discussed. In section 5, the algorithm and its analysis are presented. In section 6, we conclude this paper. 2

P (a) Given Two Polygons P and Q; I (b) Vertex-Vertex Configuration is not necessarily Minimal Area Convex Hull P X (c) Minimal Area Convex Hull Figure 1. Brute Force Algorithm may not Lead to Optimal Solution

2. Preliminaries In this section, we define terms related to the convex hull of polygons P and Q, with Q being allowed to translate counter-clockwise along the boundary of P. Among a total of N vertices, n of them belong to P. We indicate the it vertex of P, starting from a fixed vertex and indexing in a counter-clockwise order, by v. where i=1,2,....,n. The vertices vi of Q are indexed in the clockwise order, where i=n+l,n+2,....,N. (The reason for using the opposite ordering is to simplify the equation of the added area functions later.) The vertices of P and Q are stored in two doubly linked lists. We indicate the slope of the edge vivi+1 by S.. Consider the convex hull over two convex polygons P and Q in contact as illustrated in Figure 2. There exist two added polygons which constitute the difference between the convex hull and the polygons P and Q. Based on the direction of travel, one of the added polygons is in the front and the other one is in the rear. The total area of these two added polygons is the added area, which can be zero or positive. The two polygons touch each other, with one providing an edge and the other a vertex. The edge, along which Q translates, is called the current contact edge e with slope SA. The vertex v from the other polygon is called the contact vertex. In Figure 2, a contact edge is marked by a double line and a contact vertex by a circle. <Insert Figure 2> To form a convex hull of two convex polygons, new convex hull edges are needed. The new edge in the front connects two convex hull 3

Convex Hull Edge Front Added Polygon Va P Contact\ Contact Vertex Edge ec \Vert \VPB \ Convex Hull Vertex m m m --- Rear Added Polygon Direction of Transl ati on Figure 2. Convex Hull of Two Polygons

vertices, v and v. Similarly, there is one in the rear. If the pa qa convex hull vertices from P and Q coincide, we count them as two distinct vertices. Therefore, we can assume that for the general case there are always four convex hull vertices joined by two convex hull edges. Finding the minimal area convex hull of two adjoining convex polygons P and Q under translation is equivalent to finding the position of Q with minimal added area. As Q translates along a contact edge, the area of the added polygons changes. Since the added polygons can be triangulated, the change in the added area can be computed from the changes in the area of the triangles by triangle area functions, the sum of which is the added area function. In general, a triangle in a triangulated added polygon shares an edge with polygon P or Q. The shared edge will be referred to as a base edge. In some cases, triangles share two edges, one with P and the other with Q, ich are shaded in Figure 3. Selecting the base edge then depends on which polygon provides a contact edge. If the contact edge belongs to P, for the triangle in the front (or rear) added polygon, the base edge is the one which belongs to Q (or P). If the contact edge belongs to Q, we select the base edge in the opposite way. A base edge is marked by a double line in Figure 3. <Insert Figure 3> 4

P 0 Figure 3. Base Edges ( double lined ) of Triangles in the Added Polygons

3. Added Area Function In this section, we examine the added area function (AAF). The added area is the sum of triangles since it can be triangulated. To characterize AAF, first we prove that the triangle area function is linear. Based on its linearity, we derive the slope of AAF. (The reason we are interested only in the slope is due to the following observation. Whenever Q is translated by tx, the origin of AAF can be translated by the same amount. This enables us to treat the current added area as a constant term in AAF.) By examining a formula for AAF, we state the conditions when its slope changes. Finally, the piecewise linearity of AAF is asserted. As Q translates along the boundary of P, a triangle in the added area polygon exists for a certain range of the translated distance. Since the added area is the sum of the triangles in the added polygons, we can calculate AAF from the triangle area functions. Consider the area of a triangle v.ivvk when polygon Q is translated by (tx,ty) along the current contact edge ec (vavp) with slope Sp. The area of the triangle vivjvk is computed by the cross product of its two edges using the left hand rule. The cross product (viv. x vjvk)/2 is the area of the triangle vivjvk if its base edge belongs to P. On the other hand, if the base edge belongs to Q, then the area is (v v. x vivk)/2. In Figure 4, the base edge v.v. with slope S. belongs to Q and i k vk belongs to P. <Insert Figure 4> We now establish a linear relationship between area and the amount 5

Figure 4. Calculation of the Area of a Triangle

of translation by assuming that no edge has an infinite slope. (The detail for resolving an infinite slope is discussed in Section 4.) Lemma 3.1 The triangle area function of a triangle vivjvk translated along e by (tx,ty) is linear in t. Its slope is: c x y x (X - X.)(Si - S )/2, (1) where Sp is the slope of ec and S. is the slope of edge v.vj with Xcoordinates X. and X.. 1 3 [Proof] The proof is given in Appendix 1. The slope of AAF depends on the slope of the base edges and the slope of the contact edge since the slope of a triangle area function depends on the same quantities from Lemma 3.1. It is worthwhile to note that the slope of AAF does not depend on how an added polygon is triangulated. The calculation for the slope of AAF follows. We know that the sequence of edges between v p and vpa and those between vqp and va are Pt3 pa q3 qa the base edges, where vpa (or vqa) and vpp (or Vq) are the convex hull vertices belonging to P (or Q) in the front and rear added polygons, respectively. Therefore, if the current contact edge is ec (v ve), the slope of AAF is: pa-1 qa-l z (X - Xi)(Si - )/2 + (X - Xi)(Si )/2 (2) i=pp i=q3 where pa, qa, pg, and q3 are indices for the convex hull vertices and Sk is the slope of the current contact edge ec. Note that if Si and So are c i~~~~~~~~~3 6

the same, (Si - S ) is zero. This confirms that the contact edge is not used as a base edge in the calculation. Let us turn to the changes in the slope of AAF. From formula (2), we see that the slope changes if Sp changes or if the number of terms in the summation changes. The latter case corresponds to the situation when the convex hull vertex changes and the former case when the contact edge changes. The following two lemmas clarify these situations. Lemma 3.2 The slope of AAF changes if the coefficient of Sp is non-zero and the slope of the contact edge changes. [proof] In formula (2) for the slope of AAF, the coefficient of S is (X p - Xp) + (Xq - Xq). This coefficient is non-zero by pp pa qsP qa assumption. Therefore, if the value of Sp, the slope of the contact edge, changes, the slope of AAF also changes. ~ Lemma 3.3 The slope of AAF changes if a convex hull vertex changes. [Proof] If a convex hull vertex changes, the number of terms in formula (2) increases or decreases by one. In either case, the slope of AAF changes because the slope of the triangle area function of the appearing (or disappearing) triangle cannot be zero. Because both P and Q are convex polygons, the slope of the base edge cannot be the same as the slope of the contact edge. Hence, by Lemma 3.1, the change in the slope of AAF due to an appearing (or a disappearing) triangle must be nonzero. ~ Changes in the convex hull vertex are illustrated in Figure 5. In Figure 5(a) a triangle v ppvp+lvqp disappears as a convex hull vertex pP3 pP+ - iP 7

changes from vpp to vpO+l. This occurs when vqg passes the extended line of edge v pvp+l. Similarly, in Figure 5(b), as the extended line of an edge vqpvq _ passes the vertex vpp a convex hull vertex changes from vqp to vqp_ and a triangle v v vq 1 appears. It is possible that more than one convex hull vertex changes simultaneously as illustrated in Figure 5(c). The slope of AAF, then, may not change at all since it is possible that the sum of the added terms equals the sum of the deleted terms. To resolve such a case, we consider the changes of convex hull vertices one at a time. <Insert Figure 5> Now we are ready to summarize the shape of AAF. Lemma 3.2 and Lemma 3.3 imply that AAF is piecewise linear as there exist points where the slope of AAF changes. There cannot be a jump in AAF where the slope changes. If that were the case, the area at that point on the AAF would be multi-valued. This implies that the convex hull over P and Q for a particular configuration is non-unique which leads to a contradiction. Therefore, AAF is continuous at points where the slope changes. Hence, AAF is continuous piecewise linear. Since the area of the polygons P and Q is constant, finding the minimal area convex hull of P and Q is equivalent to finding the minimum in AAF. Since AAF is piecewise linear the minimum of AAF is at one of the refraction points where the slope of AAF changes. In Section 5, we develop an algorithm to find the minimal convex hull of P and Q by tracing AAF at these points. It is preceded by some initialization procedures in Section 4. 8

P QI Q P Vp13 15 (a) A convex hull vertex changes from Vpj3 to Vpj3+I: A triangle Vp3 Vp3+1 Vq3 disappears. (b) A convex hull vertex changes from Vqj3 to Vqj3-l: A triangle VpJ3 Vq j Vcqj3-1 appears. (c) Two convex hull vertices Vpj3 and Vqj3 change simultaneously to Vp3+I and Vqj3-1, respectively. Figure 5. Changes of Convex Hull Vertices

4. Initialization Before finding the minimal area convex hull, we determine the initial values of the parameters to be used in the algorithm in Section 5. First, we set the initial configuration of P and Q. Secondly, a procedure to determine the initial contact edge and contact vertex is given. Thirdly, we calculate the initial added area and determine the initial convex hull vertices. And finally, we calculate the initial slope of AAF. All of the above are done in linear time and the procedures are given in Appendix 2. 4.1 Initial Configuration of P and Q We find the initial configuration by translating Q so that a vertex of P and a vertex of Q coincide. From the coordinates of the vertices of P, we find a vertex v with the smallest Y-coordinate. Similarly, pr we find a vertex v with the largest Y-coordinate among the vertices of qr Q. (In case there is more than one such vertex, choose the one with the argest X-coordinate as v or the one with the smallest X-coordinate as pr v.) We translate Q such that vq coincides with v. We assume there qr qr pr is no edge with an infinite slope. If there is such an edge, rotating the polygons by a "small" amount about v eliminates the infinite pr slope. These steps are performed in linear time. 4.2 Initial Contact Vertex and Contact Edge The initial contact edge e. and the initial contact vertex vC may belong to P or Q. To find them we use the Procedure Find e v listed in Appendix 2. The input of the procedure is and qc the two in Appendix 2. The input of the procedure is v and v, the two pc qc 9

contact vertices from P and Q. They are initially set at vr and v, respectively. The procedure works as follows. If the left-handed cross product v v x v vp is positive, the counter-clockwise angle of qc-l qc pc pc+1 v qcv qcvpc+ is less than r. In this case, the current contact edge ec qc-l qc pc+1 c is vpc+lvpc which belongs to P and the current contact vertex v is vq pc+1. pc c qc which belongs to Q. If the cross product is not positive, e is vqcvqc-l and v is v. The same procedure is also used for finding the qc qc-1. c pc next contact vertex and contact edge. 4.3 Initial Convex Hull Vertices and Added Area While we find the initial convex hull vertices, we also calculate the initial added area in Procedure Find CHV A. The output of the procedure are {CHV}, a set of four convex hull vertices, vp, Vpo, vqa, and vq, and the current added area A. The input of the procedure are the two contact vertices v and v pr qr The procedure works as follows. For the front added polygon, starting from the contact vertices v and v as current vertices of pr qr polygon P and Q, respectively, form triangles which share their base edges with Q. Traverse the vertices of Q clockwise until no more such triangles can be formed. Move the current vertex of P to its next vertex and test whether a triangle which shares its base edge with P can be formed. If so, form it and repeat until no more triangles can be formed. Then, put the current vertices of polygons P and Q into the set of convex hull vertices. While forming the triangles, we calculate the added area by using the cross product. The same process is applied for 10

the rear added polygon by changing the direction of vertex traversal. In performing the Procedure FindCHV A, each vertex of P and Q is traversed at most once. Therefore, the time complexity of this procedure is linear in N. 4.4 Initial Slope of the Added Area Function To calculate the initial Slope_of_the_added_area_function, we use formula (2) in Section 3. To simplify updating, we use the following representation for the slope of AAF: (Cb + Cr S)/2 = Sum of constants corresponding to the base edges where Cb C = Sum of constants corresponding to the contact edge r S, = Slope of the contact edge. Then the slope of AAF has terms: pa-1 pa-1 Cb= - (Xi+ i=pp3 pc-i Cr =O (Xi+l i=pp =(X - X ) pj3 pa qa-1 Xi)Si + z (Xi+ - Xi)Si i=qP qB-l xi) - Z (Xi+l i=qa + ( - X ). qg qa - Xi) 11

5. The Algorithm and Its Analysis We are ready to present an algorithm that gives the convex hull for the two convex polygons P and Q for which the added area is minimal. The AAF is continuous piecewise linear and its slope changes at refraction points. To find the minimal area configuration, we trace only the refraction points by updating the slope in constant time. Then, the algorithm would run in linear time if there is a linear number of refraction points. We show that there can be no more than 3N of them where N is the total number of vertices in P and Q. We begin with the updating for the refraction points needed by the algorithm. 5.1 Refraction Point Due to Contact Edge Change From Lemma 3.2, when the contact edge changes, there exists a refraction point. Correspondingly, we determine the new contact edge and contact vertex. Then, we calculate the maximum distance Q can be translated along the new contact edge to reach the next refraction point. The new contact edge and contact vertex are determined by calling the Procedure Find e v explained in Section 4.2. The parameters depend on the situation. If the current contact edge belongs to P, the parameters are (ec, vv, v, v ). If the current contact edge belongs to Q, the parameters are (ec, vc, vc, vp). Once the new contact edge and vertex are determined, we calculate the X component of translated distance of Q along the new contact edge to the next refraction point, which is denoted by t. Since the xr 12

vertices of the current contact edge are v and v, txr is X - X. 5.2 Refraction Point Due to Convex Hull Vertex Change When a convex hull vertex changes, the slope of AAF changes as well. We calculate the X component of the translated distance denoted by tc along the current contact edge to reach the next refraction point. <Insert Figure 6> In Figure 6, as Q becomes Q', the convex hull vertex vqp moves to qO v -1 The amount of translation txc can be calculated from the fact!! that vpp is on the extended line of the edge vq lvq. The equation of tthe edge v v q,-l q,3 Y - Yq = Sq( - Xq). qo 3 Sqg -l qo3 (3) By replacing XqP with (Xq + t ) and inserting the coordinates of vpO refraction point due to the change of YqO with (Yqp into equation vqp + Stxc ) and by (3), we get the txc = (Sq (X - Xq) (Y - Yq ))/(Sq -1 S). (4) For the general case, we use Procedure Calculate t in Appendix 2. The - xc term tr in the procedure is explained in the previous section. 5.3 Updating the Slope of the Added Area Function The next refraction point ntc is the minimum or maximum of the xc 13

Q Q' Figure 6. Refraction Point Due to a Change in the Convex Hull Vertex

elements of {t } and tr depending on whether tr is positive or xc r xr negative. Corresponding to that refraction point, we update the slope of AAF using Procedure Update_slope_CHV in Appendix 2. The updating depends on the cause of the next refraction point. If it is caused by a change in a convex hull vertex, we update the values of Cb and Cr. If it is caused by a change in the contact edge, we only need to change S, since Cb and C depend on only the convex hull vertices. 5.4 The Algorithm and Its Time Complexity The algorithm for finding the minimum area convex hull of two convex polygons is given as Algorithm 1. Using the procedures in Section 4, we initialize the configuration of P and Q and compute the initial added area. Then, we trace the refraction points to find the minimal added area and its configuration. In this algorithm, Min {tC} xc finds the smallest element in the set {tx}; similarly, for Max {tx}. xc xc The values mA, mec, mvc, and mt store the values of A, e, v, and t, respectively, when the added area is minimal. Additionally, t is a variable for the X component of translated distance along ec from the vertex vp to the current refraction point. For the vertices of P and Q, we keep their coordinates from the initial configuration and update them. By keeping track of the amount of translation for Q, hence the translation of the coordinate system, we calculate the coordinates of a vertex under consideration in constant time. <Insert Algorithm 1> Since the time to update the values of Cb, Cr, and S0 at each refraction point is constant, the time complexity of Algorithm 1 depends 14

Algorithm 1. Find minimum area convex hull 1. Initialization Find the initial configuration of P and Q, and v and v. pr qr Find e -vc(eivcpr v qr). e 4 e.. c 1 Find CHV A ({CHV}, Ac vr v ). mA 4-A me 4-e,mv m -v, mt 4-0. c c C C C C C O Slope_of_added_areafunction({CHV},Cb,Cr). 2. Repeat t - O. c t - X - Xe xr a t3 {t } 4-0. {t xc} for each CHV in {CHV} Calculatetc(CHV, {CHV},S,tt, {tx }). while {t } ~ 0 do XC begin if (tx > 0) then nt x Min{t}. XC XC else ntxc Max{tc}. Ac Ac + (Cb + C S )ntxc/2. t 4 t + nt c c xc if (A < mA ) then c c

mA - A, me - e, mvy cv, mtV t c c c c c c c c Update_slopeCHV({CHV},ntxc,Cb,C ). t < t - nt xr xr xc for each CHV in {CHV} Calculate tXc (CHV, {CHV}, S, tr, {tc ). end A 4 A + (Cb + C S )txr/2. c c b r xr t 4 t + t c c xr if (A < mA ) then c c mA i A, me e e, mv v, mt t. c c c c c c c c if (e c p) then Find e v (ec,vc,v,vc) - c- c (c a' c else Find e Cv (e vcvc V V). Stop when e = e..

on the number of refraction points. The following lemma gives the upper limit on that number. Lemma 5.1 The maximum number of refraction points is 3N. [proof] From Lemma 3.2 and Lemma 3.3, we know that a refraction point is caused by either a change in the contact edge or a change in the convex hull vertex. Since every edge of P and Q becomes a contact edge exactly once, the maximum number of refraction points due to a change in the contact edge is N. There are four convex hull vertices, two from P and two from Q. As Q translates along the boundary of P, every vertex of P and Q becomes a convex hull vertex exactly twice, once in the front added polygon and once in the rear added polygon. Though, for the special case illustrated in Figure 5(c), there is a reduction in the number of refraction points by at most 3. Hence, there can be no more than 2N refraction points due to a change in the convex hull vertex. Consequently, the maximum number of refraction points is 3N. s In Algorithm 1, we update the slope of AAF whenever a convex hull vertex or the contact edge changes. By Lemma 5.1, the slope is updated 3N times. We can now state the theorem which gives the time complexity of Algorithm 1. Theorem 5.1 The time complexity of Algorithm 1 is linear in N. 15

6. Conclusion We have convex hull translation. the function linear in N. shown a linear time algorithm for finding the minimal area for two non-overlapping convex polygons P and Q under This is done by tracing the refraction points of AAF since is piecewise linear and the number of refraction points is If both rotation and translation are allowed, then the problem of finding the minimal area convex hull becomes more difficult. The added area function will be a three-dimensional surface with axes for area, translation and rotation. Because of rotation, AAF is expected to be sinusoidal when projected. Refraction points becomes refraction curves. If there is a linear number of such refraction curves then an algorithm with a lower bound of O(N ) time is conceivable since a linear number of refraction points along the translation axis is expected to remain. If the given polygons are not convex, the problem becomes even more difficult. 16

References [1] A. Albano and G. Sapuppo, Optimal Allocation of Two-Dimensional Irregular Shapes Using Heuristic Search Methods, IEEE Trans. System, Man, and Cybernetics, SMC-10 (1980), pp. 242-248. [2] B. Chazelle, The Bottom-Left Bin-Packing Heuristic: An Efficient Implementation, IEEE Trans. Computers, C-32 (1983), pp. 697-707. [3] H. Freeman and R. Shapira, Determining the Minimum Area Incasing Rectangle for an Arbitrary Closed Curve, Comm. ACM, 18 (1975), pp. 409-413. [4] P. C. Gilmore and R. E. Gomory, Multistage Cutting Stock Problems of Two or More Dimensions, Operations Research, 13 (1965), pp. 94 -120. [5] R. Graham and F. Yao, Finding the Convex Hull of a Simple Polygon, J. of Algorithms, 4 (1983), pp. 324-331. [6] D. S. Johnson, Near-Optimal Bin Packing Algorithms, Technical Report MAC TR-109, Project MAC, MIT, Cambridge, Massachusetts, 1973. [7] S. Israni and J. Sanders, Two-Dimensional Cutting Stock Problem Research: Review and a New Rectangular Layout Algorithm, J. of Manufacturing Systems, 1 (1982), pp. 169-182. 17

Appendix 1. Proof of Lemma 3.1 We compute the area of a translated (new) triangle as a function of the area of the old triangle. Here we use the same notations defined in Section 3. If the base edge of the old triangle belongs to P, the area of the new triangle v.vjv is: k (viVj x vjvk)/2 (((X, Yj) - (Xi Yi)) x ((, Yk)- (Xj, Y)))/2,! Expressing Xk as (Xk + tx) and Yk as (Yk + Sotx), we have: (((X, Y) - (Xi, Yi)) x ((( X + tx)(Yk + St)) - (Xj, Y )))/2 Expanding the cross product, we have: ((Y -Yi) ( -Xj) - (Xj- X) (Yk Y) + (Yj- Yi) t - (Xj- Xi) S t)/2 The sum can be expressed in terms of the area of the old triangle v.vjvk as: ((Xj - X, Y. - Y) x (Xk Xj' Y j))/2 + ((Y- i) tx - (X - X) S t)/2 (viv x jvk)/2 + ((X - X) S t - (Xj - X.) S t )/2 1 I j kj i 1 IX J i x = (vivj x Vjk)/2 + (Xj - Xi) (S. - S ) tx/2 area of the old triangle + area change = area of the old triangle + area change Ai

Similarly if the base edge of the old triangle belongs to Q, the I I area of the new triangle vivjvk can be expressed in terms of the area of vivjv as: (v V. x vV)/2 JLi ivk)/2 = (vjvi x viv)/2 + (Xj - X.) (S S) tx/2 Ji 1 ivk 3 i 1 X Since there are only two kinds of triangles in the added area polygons, the above results prove the Lemma 3.1. ~

Appendix 2. Procedures Procedure Find eCVC (eCv,v Vqc) begin cross_product 4 vqcqc x Vp cV+ if (cross_product > 0) then e - vp v, v v. c pc+ pc c qc else e v v vqc-l' v c q q- c pc end A3

Procedure Find CHV A ({CHV},A,V,v ) begin { checking front added polygon } v < v, v - v. pc pr qc qr A - 0. c p cross_product c vqc+lv x v vpc+l. if (p crossproduct > 0) then v 4 V pc pc+l' if (p_cross_product = 0) then Vc Vc+l' Vqc Vqc+l' Pcrossproduct - 1. PC pc+1' qc qc+1' while (p_cross_product > 0) do begin qcross_product v qc+vqc x v v qc+l qc qc pc while (q_cross_product > 0) do begin A 4- A + qcross_product/2, vqc 4 Vqc+l c c qc qc+1 q_crossproduct 4 Vqc+lVqc x VqcVp. end p_cross_product 4 v v x v v qc pc pc pc+l' if (p_cross_product > 0) then A 4 A + p crossproduct/2, Vpc - Vpc+. end v - v, v - v. pa pc qa qc {CHV} - {Vp, vqa}.

{ checking rear added polygon } V V, V - V. pc pr' qc qr pcrossproduct v- vpc_ x Vqqc-q if (p_crossproduct > 0) then v - V pc pc-i' while (p_cross_product > 0) do begin qcross_product - v v x v v pc qc qc qc-l while (q_cross_product > 0) do begin Ac - A + q_cross_product/2, Vqc Vqc-l q_cross_product 4 v vq x v vq pc qc qc qc-l' end p_crossproduct pv c-lvp x VpcVqc if (p_cross product > 0) then A - A + p crossproduct/2, v pc Vpc-. c c pc pc-i end v ~- v v - v Vpt Vpc, Vqp qc { CHV} {CHV} + {Vp,Vq}. end

Procedure Slope_ofaddedareafunction({CHV},Cb,C ) begin Cr - (Xp - + Xq - Xqa) Cb - 0. i - Vpp. while (i < v ) do pa begin Cb Cb + (Xi+ - Xi) Si i i + 1. end i 4 vq while (i < v ) do qa begin Cb Cb + (Xi+ Xi) i i i +l. end end A6

Procedure Calculate t (CHV,{CHV},S,,t, {tx} ) - xc xr xc begin case CHV of pa a = ( pa Xq a pa / ( pa) Vp: t = (Spp(Xq - XpP - (Yq )) / (S - S) v: t =(S (X - ) - (Y - )) / (S -S ) qa xc a- pa qa pa qa qa-1 Vq: tc = (S q_(Xp- Xq (Y - Yq) ) / (Sq-1 - S) end if (tx > 0) then if (0 < tx txr) then {t } - {t } + t. xelse if (tx t 0) then {txc xc xc else if (txr _ xc O) then {t I} - {txc} + t xr xc xc ~xc xc end "P7

Procedure Update slope CHV({CHV},nt rC,C ) begin case nt of xc pa: Cb Cb + (Xpa+l Xpa )Spa C C -(X -x ). r r pa+l pa pa pa+l. v: 4- C 1X - )S p: Cb Cb - Xp+l p- )Sp Cr Cr + (Xpp+l - Xpp PP Pp+1+ PC 4- C+(X -X )S. va: C Cb - (Xqa - Xqa- )Sqa-li Cr Cr (Xqa Xqa -l) V <-V qa qa-l. v q: Cb Cb + (Xqo - Xql)S q-l Cr Cr (X - Xql.) VqP VqO_1l end end tA8