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 Dept. of Industrial & Operations Engineering Tech. Report #86-3

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 January 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

Abstract Given two non-overlapping convex polygons P and Q, we find their relative position 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 are able to determine the minimal area convex hull in O(N) time. Instead of computing the convex hull after every translation, we compute the slope of the added area function 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.

List of Symbols A: Added area of the current configulation. c A.: Minimal added area. min at: Adjacent refraction point in {t }. xc xc Cb: Sum of constants corresponding to the base edges in the slope formula of the added area function. CHV: Convex hull vertex. {CHV}: Set of CHV. C: Sum of constants corresponding to the current reference edge in the slope formula of the added area function. e: Current reference edge. c e.: Initial reference edge. me: e when the added area is minimal. 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. P, Q: Convex polygons. Si: Slope of the edge vvi+l. Sp: Slope of the reference edge ec (vav ). t: X component of the translated distance along e from the c c vertex v3 to the current refraction point. t (t ): X(Y) component of the translated distance along ec from the current refraction point. txc: X component of the translated distance along ec from the XC C

current refraction point to the next refraction point due to a change in the convex hull vertex. {txc: Set of tc. tx: X component of the translated distance along ec from the current refraction point to the vertex v. ~th v.: ih vertex of P and Q for i=1,2,....,N. v (v ): Convex hull vertex belonging to P(Q) in the front added pa qa polygon. vpp(vq): Convex hull vertex belonging to P(Q) in the rear added polygon. v (V): Current vertex of P(Q). v r(vqr): Initial touching vertex in P(Q). v (v ): Vertex of the reference edge ec in the front (rear) added polygon. v: Current reference vertex. c X.(Y.): X and Y coordinates of vi.

List of Figures Figure 1. Added Area Function Figure 2. Convex Hull of Two Polygons Figure 3. Special Case Configurations of Convex Hull Figure 4. Base Edges of Triangles in the Added Polygons Figure 5. Notations for Convex Hull Figure 6. Calculation of the Area of a Triangle Figure 7. Changes of a Convex Hull Vertex Figure 8. Special Case: More than One Convex Hull Vertex Changes Figure 9. Candidate Angles of Rotation Figure 10. Reference Edge and Vertex Figure 11. Refraction Point Due to a Change in the Convex Hull Vertex Figure 12. Finding New Reference Edge and Vertex

List of Procedures Procedure Find e vc (ecV' pc'vqc) Procedure Find CHV A ({CHV},A,v rqr) Procedure Slope_of_added_area_function ({CHV},CbCr) Procedure Calculate txC (CHV, {CHV},S, tx, {tx} ) Procedure Update slopeCHV ({CHV},atqd(xc),Cb,C ) Algorithm 1. Find minimum area convex hull

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). One criterion for classifying the problem is the shape of the material to use. If the shape is linear, planar, or spatial, then the problem is considered a one-dimensional, two-dimensional, or three-dimensional problem, respectively. We shall restrict our attention to two-dimensional problems. An interesting two-dimensional problem is the packing of shapes. The shapes can be rectangular or non-rectangular. The packing of 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 [2]. For non-rectangular shapes, it is reasonable to expect even greater difficulties. Recent solutions for rectangular shapes have employed heuristics [2,7]. For non-rectangular shapes, very few papers are published. One approach to simplify the packing of non-rectangular shapes is preprocessing them by circumscribing with rectangles [1] and packing the resulting rectangles [3]. However, this preprocessing produces more waste than packing with the original shapes. Therefore, we try to develop more efficient preprocessing algorithm by clustering the original shapes by two, especially two convex polygons. In this paper, we consider the problem of packing two convex polygons of given orientations under translation such that the convex

hull over the two polygons is minimal in area. If a polygon is nonconvex, we can apply a linear time algorithm to find its convex hull [5]. To reduce the waste, we seek the minimal area convex hull of two convex polygons P and Q with Q being allowed to translate along the boundary of P. Since Q is allowed to translate, there are at least O(N) possible configurations, where N is the total number of vertices of P and Q. For each configuration of P and Q, their convex hull can be found in O(N) time [8]. Hence, brute force leads to an algorithm that would run in at least 0(N ) time. 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 as shown in Figure 1.1. Exploiting the piecewise linearity of the added area function, we find the minimal added area configuration by calculating the added area 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 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 that the total number of refraction points is O(N). <Insert Figure 1.1> This paper is organized as follows. In section 2, definitions and 2

Added Area Transl ati on Figure 1.1 Added Area Function

notations are introduced. In section 3, the added area function is examined. In section 4, initialization processes are discussed to find the minimal area convex hull. In section 5, a linear time algorithm and its analysis are presented. In section 6, we conclude this paper. 3

2. Definitions and Notations In this section, we introduce the definitions related to the convex hull of convex polygons P and Q, with Q being allowed to translate counter-clockwise along the boundary of P. Then, we introduce the notations for the convex hull and for the vertices and edges of P and Q. 2.1 Definitions To find the minimal area convex hull of two convex polygons, we define terms we will use including (1) reference edge and vertex, (2) convex hull edges and vertices, (3) front and rear added polygons, (4) triangle and added area functions, and (6) base edge. (1) Reference edge and vertex: Consider the convex hull over two adjoining convex polygons P and Q as illustrated in Figure 2.1. The two adjoining convex polygons touch each other, with one polygon providing an edge and the other a vertex. The edge, along which Q translates, is called a reference edge. The vertex from the other polygon is called a reference vertex. In Figure 2.1, a reference edge is marked by a double line and a reference vertex by a circle. <Insert Figure 2.1> (2) Convex hull edges and vertices:To form a convex hull of two convex polygons, new edges are needed. Each new edge connects two vertices, one vertex from P and the other from Q. The new edges are called convex hull edges and the vertices are convex hull vertices. In general, there are two convex hull edges joining four convex hull vertices. For some cases, the convex hull vertices from P and Q 4

Convex Hull Edge Front Added Polygon Reference\ Reference Vertexl Edge \a/ IQ Direction of Translation Convex Hull Vertex Rear Added Polygon Figure 2.1 Convex Hull of Two Polygons

coincide as illustrated in Figure 2.2. In these cases, we count them as two distinct vertices. Therefore, we can assume that for the general case there are always exactly four convex hull vertices. <Insert Figure 2.2> (3) Front and rear added polygons: Once a convex hull of polygons P and Q is formed, there exist two added polygons which are the difference between the convex hull and the polygons P and Q. One of the added polygons is a front added polygon and the other one is a rear added polygon. The front added polygon is the one in the direction Q translates. The area of these two added polygons is an added area. The added area can be zero or positive. (4) Triangle and added area functions: 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 reference 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. The changes in the area of triangles are described as triangle area functions. The sum of the triangle area functions in the added area is an added area function. (5) Base edge:In general, a triangle in a triangulated added polygon shares one entire edge with polygon P or Q (see Figure 2.3). The shared edge will be referred to as a base edge. In some cases, triangles share two entire edges with polygons P and Q, one with P and the other with Q. In these cases, selecting the base edge depends on 5

Convex Hull Vertices Figure 2.2 Special Case Configurations of Convex Hull

which polygon provides a reference edge. If the reference 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 reference edge belongs to Q, we select the base edge in the opposite way. <Insert Figure 2.3> 2.2 Notations Now we introduce the notations for (1) vertices of polygons P and Q, (2) edges of polygons P and Q, (3) the data structure of vertices, (4) the convex hull vertices, (5) the reference edge, and (6) the reference vertex. (1) Vertices of polygons P and Q: We assume that the total number of vertices of polygons P and Q is N. Among the N vertices, n vertices belong to polygon P. Hence, Q has N - n vertices. We indicate the ith vertex of polygon P, starting from a fixed vertex and indexing in a counter-clockwise order, as v. where i=1,2,....,n. Also, v. stands for 1 1 th the i- vertex of polygon Q, starting from a fixed vertex and indexing in a clockwise order, where i=n+l,n+2,....,N. The reason for using the opposite ordering is to simplify the equations of the added area functions. The X and Y coordinates of a vertex v. are denoted by (XiYi). (2) Edges of polygons P and Q: We indicate an edge by using the notations for vertices. The i- edge of a polygon is v.v.i and its slope is S.. (3) The data structure of vertices: The vertices of P and Q are 6

II \ i Figure 2.3 Base Edges ( double lined ) of Triangles in the Added Polygons ~~ ~~igure 23BsEds(duin e ) o

separately stored as doubly linked lists. In the lists, the next (or previous) vertex of a given vertex v. is v. (or v. ) The next (or. 1+1 1- 1 previous) vertex is decided in cyclic order, i.e., the next (or previous) vertex of vn (or v1) of P is v1 (or vn) and the next (or previous) vertex of vN (or v n+) of Q is vn1 (or vN). (4) The convex hull vertices:To indicate the convex hull vertices, we introduce a special notation. We indicate the vertices as v. If a convex hull vertex belongs to polygon P (or Q), we include p (or q) in the subscript of v and if the vertex belongs to the front (or rear) added polygon, we include a (or P) in the subscript of v. Therefore, the convex hull vertices are denoted by v p, vp, vqa, and vqs. The locations of these vertices are illustrated in Figure 2.4. <Insert Figure 2.4> (5) The reference edge: We classify the reference edge as initial reference edge and current reference edge and indicate these edges as ei and e, respectively. For the current reference edge ec, we indicate its two vertices as v and vp, where v (or vp) is the vertex belonging to the front (or rear) added polygon. Since v is the next vertex of v, the slope of the current reference edge ec is SP. (6) The reference vertex: For the reference vertex, we introduce only the current reference vertex and indicate this vertex as vc. 7

pB(pxpjS,YP) Vpa(xpa,pa) [ \ ^l I.Yq Va( Figure 2.4 Notations for Convex Hull I / I l I / I \ / 1 VqA(x~jAY9A> Vqa~x9iaYqia Figure 2.4 Notations for Convex Hull

3. Added Area Function In this section, we examine the added area function. The added area function is a sum of the triangle area functions since the added area can be triangulated. To characterize the added area function, first we prove that the triangle area function is linear. Based on the linearity, we derive the slope of the added area function. Then, by examining the slope formula, we exploit the conditions when the slope of the added area function changes. Finally, piecewise linearity of the added area function is discussed. 3.1 Triangle Area Function As a basis of the added area function, we examine the triangle area function as Q translates counter-clockwise along the boundary of P. First, we define a triangle under consideration. Then, the method to calculate the triangle area is explained. Finally, we characterize the triangle area function of a translated triangle as Q translates along the reference edge. We consider the area of the translated triangle of a triangle vi.vvk when polygon Q is translated by (tx,ty) along the current reference edge ec (vavi) with slope S,, where tx (or ty) is the X (or Y) component of the translated distance. We assume that the base edge of the triangle vjvkv is v.v.. Since v.v. is the base edge, both vertices I j k. 3 1z3 v. and v. belong to the same polygon P or Q and vk belongs to the other 1 J polygon. We assume v. is the next vertex of v. in the same polygon. Therefore, the slope of the base edge v.v. is S.. The translated triangle can be denoted by v.vjvk if the base edge v.v. belongs to 8

I 1 polygon P and denoted by vivjvk if the base edge belongs to Q. The area of a triangle v.vjvk is computed by the cross product of 1 j k its two edges. The cross product is taken using left hand rule. The cross product (v.vj x vjvk)/2 is the area of a triangle v.vjvk if its i j j k i 3 k 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 the following Lemma 3.1, we assume that no edge has an infinite slope. The details for resolving an infinite slope are discussed in Section 4. Lemma 3.1 The triangle area function of the translated triangle of vivjvk along ec by (tx,ty) is linear in t. Its slope is: (X. - X)(S4 - S )/2. The proof is given in Appendix. Lemma 3.1 can be illustrated as follows. Consider a triangle vn+lvn+2v in Figure 3.1. The slope of its triangle area function is: (Xj - X.i)(S. - S)/2 (X - X )(S - S2)/2 n+2 n+ l n+1 2 where Sn+1 is the slope of the base edge vn+lvn+2, and S2 is the slope of the reference edge v2v3. <Insert Figure 3.1> 9

V1( P.I~~~~~~tI:!+/Vn+2 Sn+11 Vn + 1 u 3Vn+. C tl o t Figure:3.1 Calculation of the Area of a Triangle

As Q translate along the boundary of P, a triangle in the added area polygons exists for certain range of the translated distance of Q. Therefore, a triangle area function is a line segment defined in this range. 3.2 Slope of the Added Area Function Since the added area is a sum of the triangles in added polygons, we can calculate the added area function from triangle area functions. The added area polygons includes the same triangles for certain range of the translated distance of Q. In the range, the added area function is linear from Lemma 3.1. We calculate the slope of the added area function for a configuration of P and Q. The slope of the added area function depends on the slope of the base edges and the slope of the reference edge since the slope of a triangle area function depends on the slope of the base edge and the slope of the reference edge from Lemma 3.1. It is worthwhile to note that the slope of the added area function does not depend on how the added area polygons are triangulated. If we know which edges of polygon P and Q correspond to the added polygons and which edge is the reference edge, we can calculate the slope of the added area function. To calculate the slope of the added area function, we need to know the base edges and the reference edge. From the definition of convex hull vertices, we know that the edges between vpp and vpa and between vqO and vq belong to the added polygons and these edges are the base edges, where vpa (or vqa) and vp (or v q) are the convex hull vertices belonging to P (or Q) in the front and rear added polygons, 10

respectively. Therefore, if we assume the current reference edge is e (v v ), the slope of the added area function is: a3 pa-1 qa-1 (X. Xi)(S. - 5 )/2 + (Xi - X.)(S - )/2 i=p + i. i=q i+ where pa, qa, pp, and qp are the indices for the convex hull vertices and Sp is the slope of the current reference edge ec. Note that if Si and Sp are the same, (Si - S ) is zero. This implies that the reference edge is not used as a base edge. 3.3 Change in the Slope of the Added Area Function Let us examine the change in the slope of the added area function. From the formula in Section 3.2, we can see the slope changes if the number of terms in the summation changes or S changes. The former case corresponds to situation when the convex hull vertex changes and the latter case when the reference edge changes. The following two lemmas 3.2 and 3.3 clarify the conditions when the slope of the added area function changes. Lemma 3.2 The slope of the added area function changes if a convex hull vertex changes. [proof] If a convex hull vertex changes, the number of terms in the slope formula of the added area function increases by one or decreases by one. In either case, the slope of the added area function 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 11

be the same as the slope of the reference edge. Hence, by Lemma 3.1, the slope of the area function of an appearing (or a disappearing) triangle must be nonzero. - A change in the convex hull vertex is illustrated in Figure 3.2. In Figure 3.2(a) a triangle v pvpp+lvq, disappears as a convex hull vertex changes from v to Vp0+l. This occurs when vqO passes the extended line of edge v ppvpp+. Symmetrically, in Figure 3.2(b), as the extended line of an edge vqpvqp _ passes the vertex vpp, a convex hull vertex changes from v q to vq _, and a triangle vppvqpvqp 1 appears. <Insert Figure 3.2> A special case occurs if more than one convex hull vertex changes simultaneously as illustrated in Figure 3.3. In this special case, the slope of the added area function may not change since occasionally the sum of the adding terms can be same as the sum of the deleting terms. To resolve such a case, we consider the changes of convex hull vertices one at a time. Therefore, in general, the slope of the added area function changes whenever the convex hull vertex changes. <Insert Figure 3.3> Lemma 3.3 The slope of the added area function changes if the coefficient of Sp is not zero and the slope of the reference edge changes. [proof] In the formula of the slope of the added area function, the coefficient of Sp is (XpP - Xp) + (XqP - Xq). This coefficient is not zero by assumption. Therefore, if the value of Sp changes, 12

P, — Q. VPB Vpj~.... Vq6 (a) A convex hull vertex changes from Vpj to Vp++1: A triangle Vpj3Vpj+1Vqj3 disappears. P / 0Q =.*q l3 * vq3-1 Vpj-3 q Vq - Vq13-1 (b) A convex hull vertex changes from Vqj3 to Vq3 —1: A triangle VpBVq^1 Vq3-1 appears. Figure 3.2 Changes of a Convex Hull Vertex

VpB p Pi 3+li1 VqB VqB3 SQB VqB-1VB-113-1 / * *' X \Q QGoQo Two convex hull vertices VpBj and Vq3 change simultaneously to Vpj+1 and Vq3-1, respectively. Figure 3.3 Special case: More than one convex hull vertex changes

i.e. the slope of the reference edge changes, the slope of the added area function changes. ~ 3.4 Shape of the Added Area Function Now we are ready to characterize the shape of the added area function. Lemma 3.2 and Lemma 3.3 imply that the added area function is piecewise linear since there exist points where the slope of the added area function changes. Since the area of a configuration is unique, there can not be a jump in the added area function where the slope changes. Therefore, the added area function is continuous at points where the slope changes. Hence, the added area function 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 the added area function. Since the added area function is piecewise linear the minimum of the added area function is at one of the refraction points where the slope of the added area function changes. Therefore, by tracing the area at the refraction points, we can find the minimal area convex hull of P and Q. In the following sections, we develop an algorithm to find the minimal convex hull of P and Q in linear time. 13

4. Initialization To find the minimal area convex hull, we set the initial values of the parameters to be used in an algorithm in Section 5. First, we set the initial configuration of P and Q. Second, a procedure to determine initial reference edge and reference vertex is presented. Third, we calculate the initial added area and determine the initial convex hull vertices. Finally, we calculate the initial slope of the added area function. All of the above are done in linear time. 4.1 Initial configuration of P and Q We find the initial configuration of P and Q by translating polygon Q so that a vertex of P and a vertex of Q coincide. In such configuration, there can be edges with an infinite slope. A method to avoid infinite slopes is discussed. First, we find the initial touching configuration of P and Q. From the coordinates of the vertices of P, we find a vertex v with the pr smallest Y-coordinate. Similarly, we find a vertex v with the largest gr Y-coordinate among the vertices of Q. In case there is more than one such vertices, choose a vertex with the largest (or the smallest) Xcoordinate for v (or v ). We translate Q such that v coincides pr qr qr with v. pr In this translated configuration, there can be edges that have an infinite slope. However, there can be at most four such edges, two from P and two from Q, because of the convexity of the two polygons. If both P and Q are rotated by a "small" amount about vpr, then no edge will 14

have an infinite slope. The angle of rotation is one half of the minimum of the four angles -- Oi, oj, k, and 8m -- between a vertical line and the four edges which end or start at the vertices of P or Q, respectively, with the smallest and the largest X-coordinates. It is illustrated in Figure 4.1. If there are edges with an infinite slope, the vertices with the largest or the smallest X-coordinate is not unique. In this case, if the vertices belong to P (or Q), we choose the vertex with the smallest (or the largest) Y-coordinate. This is performed in linear time. <insert Figure 4.1> 4.2 Initial Reference Vertex and Reference Edge To translate polygon Q along the boundary of polygon P, there should be an edge and a vertex which provide the direction and position along which Q translates. The edge is the reference edge and the vertex is the reference vertex. We develop a procedure to find the reference edge and the reference vertex for an initial configuration of P and Q. Initial reference edge and reference vertex may belong to P or Q depending on their relative orientations. The two situations are illustrated in Figure 4.2, where the reference edge is marked by a double line and the reference vertex by a circle. <Insert Figure 4.2> To determine the initial reference edge and vertex, and to determine the new reference edge and vertex to be used in Section 5, the Procedure Find e v is provided. The output of the procedure is e and v, which - c- c c c indicate the determined reference edge and reference vertex, 15

af^i Vj+. i / /Prj - Vi+l / VKm |K Q / aO I. VemRi Figure 4.1 Candidate Angles of Rotation

/ p Vpr+i Vqr- o / (a) Reference Edge Belongs to Polygon P Figue < 42 Vpr+1 Vp Vqr-1 Vr1 Q (b) Reference Edge Belongs to Polygon Q Figure 4.2 Reference Edge and Vertex

respectively. The input of the procedure is vp and v, which are two touching vertices from P and Q, respectively. In the procedure, the cross product is taken using the left hand rule. <Insert Procedure Find e v > - c- c The procedure works as follows. If the cross product vqc vc x qc-l qc v v Cv is positive (Figure 4.2(a)), the counter-clockwise angle of pc pc+l v v v is less than r. In this case, current reference edge e qc-1 qc pc+l c is v v which belongs to P and current reference vertex v is v pc+l pc c qc which belongs to Q. If the cross product is not positive (Figure 4.2(b)), e is qcvqc- and v is vp c qc qc-1 c pc In the initial configuration, the touching vertices are vp and pr v. With these vertices as an input, we can determine the initial qr reference edge and reference vertex by calling the procedure with parameters (ei, vc, vpr vqr). The output ei also represents the current reference edge e. 4.3 Initial Convex Hull Vertices and Added Area To start to find the minimal area convex hull of P and Q, we need to find the initial convex hull vertices and added area. While we find the initial convex hull vertices, we can calculate the initial added area. For these purposes, Procedure FindCHV A is provided. In the procedure, a p-cross-product is for the area of a triangle which shares the base edge with P while a q-cross-product is for a triangle which shares the base edge with Q. {CHV} is the set of four convex hull vertices, vpa, vp, vqa, and vq. Ac stands for the current added area. 16

Procedure Find ec-Vc(e cpc,' qc) begin cross-product 4 Vqc-_lqc x VpcVpc+l. if (crossproduct > 0) then e C v Vpc, v P v. c pc+lvpc' qc else e C v qcqc-V c V end pc end

<Insert Procedure Find CHV A > The procedure works as follows. For the front added polygon, starting from the touching vertices vp and vq as current vertices of polygon P and Q, respectively, form triangles which share the base edge with Q by traversing the vertices of Q clockwise until no more such triangle can be formed. Move the current vertex of P to the next vertex and test whether a triangle which shares the base edge with P can be formed. If it is possible, form it and restart to form triangles which share the base edge with Q starting from the current vertex of Q. Repeat this process until no more triangle can be formed. Then, put the current vertices of polygons P and Q into the set of convex hull vertices. While forming the triangles, using the cross product, calculate the added area. The same process is applied for the rear added polygon by changing the direction of traversing the vertices. While performing the Procedure Find CHV_A, every 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 the formula in Section 3.2. To simplify the updating the slope, we introduce a representation for the slope. We represent the slope of the added area function as: (Cb + Cr S )/2 where 17

Procedure Find CHV A ({CHV},A,vr,v ) - - c c pr qr begin { checking front added polygon } V - V V v. pc pr qc qr A 4 0. C p_cross_product 4 vqc+l x V pC - qc+ qc pc pc+l if (p_cross_product > 0) then v 4 v. pc pc+l' if (p_cross_product = 0) then Vc P Vpc+l' qc Vqc+l' P-crossProduct - 1. while (p_cross_product > 0) do begin qcrossproduct - v qc+l x v vpc qc+J qc qc pc while (qcross_product > 0) do begin A 4- A + q cross product/2, v Vqc+l c c - -qc qc+1 q_crossproduct - vq lv x v v qc+l qc qc pc end p_cross_product - v v x v v ~- -r qc pc pc pc+l' if (p_cross_product > 0) then A - A + p_crossproduct/2, Vpc v 1 end V - v,P V f- v. pa p c qa qc {CHV} 4 {vpa,vqa}.

{ checking rear added polygon } v 4- v v 4- v pc pr qc qr p_cross_product - vpclVpc x Vqcqc-l. if (p_cross_product > 0) then v 4- v 1 pc pc-1' while (pcrossproduct > 0) do begin qcross_product 4- v v x v v pc qc qc qc-l' while (q_cross_product > 0) do begin A 4- A + qcross_product/2, v V- Vqc c c qc qc-1 qcross-product 4- vc x qcvqc-l pc qc qc qc-1 end p_crossproduct 4- v v x v v ~- = -- ~ pc-1 pc pc qc if (p_cross_product > 0) then A 4- AC + p crossproduct/2, v 4- Vpc 1 end V 4-V,V V ~ Vpj Vpc' Vqq Vqc {CHV} 4- {CHV} + {vp, vq}. end

Cb = Sum of constants corresponding to the base edges Cr = Sum of constants corresponding to the reference edge S0 = Slope of the reference edge then the slope of the added area function shown in Section 3.2 have terms: pa-1 qa-1 Cb = (i+ - Xi)S + z (Xi+l - Xi)S i=pp i=qB pa-1 qP-1 Cr = (X -Xi) z ( Xi i=pB i=qa =(X - Xa ) + (Xq X ) pp pa qp ga A procedure to calculate the slope of the added area function using above formula is given in the Procedure Slopeof added area function. <Insert Procedure Slope_of_added_area_function> 18

Procedure Slope of added area function({CHV},CbC ) begin Cr 4 (Xpp X pa + (X - Xqa) Cb 0. i vppO. while (i < v ) do pa begin Cb 4 Cb + (Xi+1 -Xi) Si. i - i + 1. end i 4 vqi. while (i < v ) do qa begin C. 4 Cb + (Xi+ - Xi) S. b b 1 i( X X i - i + 1. end end

5. The Algorithm and Its Analysis We are ready to present an algorithm that gives the minimal area configuration. The minimal area convex hull for the two convex polygons P and Q corresponds to the configuration in which the added area is minimal. The added area function is piecewise linear and the slope of the function changes at refraction points. To find the minimal area configuration, we trace only the refraction points of the added area function by updating the slope of the function in constant time. We discuss the method to trace the refraction points and to update the slope of the added area function. Now, the algorithm would then run in linear time if there is 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. 5.1 Refraction Point Due to Convex Hull Vertex Change If a convex hull vertex changes, then the slope of the added area function changes as well. There exists a refraction point corresponding to this change. We present a method to calculate the X component of the translated distance of polygon Q along the current reference edge to reach the refraction point. We denote the X component of the translated distance as t xc <Insert Figure 5.1> In Figure 5.1, as Q becomes Q', the convex hull vertex vqO moves to v.q_. The amount of translation txc can be calculated from the fact t 9 that vp is on the extended line of the edge vqp lv. The equation of 19

I/ \I E;txr txc Vqj-l Vq3-l Q Q' Figure 5.1 Refraction Point Due to a Change in the Convex Hull Vertex

I I the edge vqplvqp is: I t Y Yq = SP- (X- Xq). By replacing XqP with (Xqp + tc) and YqP with (Yqp + SPtxc), we get: Y- (Yq0 + Sptc) = Sq (X -(X + txc)). By inserting the coordinates of v into the equation, we have: PP P -(Yq0 + Stxc) Sq-l(XpP - (XqP + tc)). Then, the refraction point due to the change of v q can be calculated: tc = (Sqp l(Xp - Xq) - (Ypp - YqP))/(SqPl - S). For the general case, we provide the Procedure Calculate t. In the procedure, txr is the X component of the distance Q translates along the current reference edge, and it is explained in the next section. <Insert Procedure Calculate t > - xc 5.2 Refraction Point Due to Reference Edge Change From Lemma 3.3, if the reference edge changes, there exists a refraction point corresponding to this change except some special cases. The special cases are the coefficient of Sp is zero and Sp remains unchanged. We determine the new reference edge and reference vertex when the reference edge changes. Then, we calculate the maximum distance the polygon Q can be translated along the new reference edge. 20

Procedure Calculate txc(CHV, {CHV},S,txr, {t }) begin case CHV of pa: c (Spaxqa pa) - Yqa - Ypa) / pa Vp t (S X- (Yq - Y p ))) / (S - Sp) qa x: c = (Sqa- (Xpa - Xqa) - Ypa - Yqa) / (qa-1 - S v: tc = (S q (X - Xq) - (Yp) - Yq)) / (SqOl -S) end if (t > 0) then if (0 < txC < tr ) then {txc} {t} xc tx. else if (t r tx 0) then {t } - {t } + t. end

The new reference edge and reference vertex are determined by calling the Procedure Find e vc provided in Section 4.2. The parameters depend on the situations. As illustrated in Figure 5.2, if the current reference edge belongs to P (case (a) and (b)), the parameters are (ec, vc, v, Vc). If the current reference edge belongs to Q (case (c) and (d)), the parameters are (e, Vcf vc, v ). As a result of calling the procedure, we get the new current reference edge and vertex. Once the new reference edge and vertex are determined, we calculate the X component of translated distance of Q along the new reference edge to the next refraction point, which is denoted by txr. Since the vertices of the current reference edge are v and v t is X - X a (5 txr a <Insert Figure 5.2> 5.3 Updating the Slope of the Added Area Function The next refraction point is the adjacent refraction point in the direction Q translates from the current refraction point. The next refraction point is the minimum (or maximum) of the elements of {t } xc and t if t is positive (or negative). Corresponding to the refraction point, we update the slope of the added area function. The updating of the slope of the added area function depends on the cause of the refraction point. If the next refraction point corresponds to a convex hull vertex change, we need to update the values of Cb and Cr. For the general case of this change, Procedure Update_Slope_CHV is 21

P VQVa. \) p va Qve Q v j V3 (a) P -— ) P (b) P - Q cp vn a d) )Q (C) Q -- P (d) Q -- Q Figure 5.2 Finding New Reference Edge and Vertex

provided. In this procedure, atc stands for the next refraction point xc among the elements of the set {txc}. If the next refraction point corresponds to the reference edge change, we only need to change Sp. Even if the reference edge changes, the value of Cb or Cr does not change since it depends on only the convex hull vertices. <Insert Procedure Update_Slope_CHV> Note that, whenever Q is translated to the next refraction point, the origin of the added area function is moved along X-axis by X component of the translated distance. This enables us to use the current added area as a constant term in the added area function. Therefore, we only need to update the slope of the added area function. For the coordinates of vertices of P and Q, we keep the coordinates of the initial configuration. By keeping track the movement of origin and the translation of Q, we can calculate the coordinates of vertices we need in constant time. In the algorithm given in the next section, we assume the coordinates of P and Q is the updated coordinates. 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 (or Max) {tc} finds the smallest (or largest) element in the set {t }. xc xc A., me, mvc, and mt are the value of A, ec, vc, and t, mmnc c c c c c c respectively, when the added area is minimal. Here, t is a variable to 22

Procedure Update slope_CHV( {CHV},atxc, CCr) begin case at of XC v:C 4- +(X x )S pa: Cb Cb + (Xpa+l pa pa C *C -(X -x ). r r (Xpa+l pa pa pa+l vo:Cb Cb - (Xpl - )S pf b b pfi+l pfi pfi Cr Cr + (Xpp+l -XP VP C Vpf+19 p(3 p,3+3 v a Cb Cb - (Xqa- Xa-l)Sqa-l. c C + (X -X ). r r Xr qa qa-l V - v qa qa-i vq:Cb Cb + (Xqp - Xq-l )SqO-l' C -Cr- (Xs - Xq ) r r q 3 q-l1 VqP Vqp-1' end end

keep track of the X component of translated distance along ec from the vertex v0 to the current refraction point. Since the time to update the values of Cb, Cr, and Sp at each refraction point is constant, the time complexity of Algorithm 1 depends on the number of refraction points. The following Lemma 5.1 gives the limit of the number of refraction points. 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 a change in the convex hull vertex or a change in the reference edge. 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. For the special case as illustrated in Figure 3.3, 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. If there are no special cases, the slope of the added area function changes whenever the reference edge changes. Since every edge of P and Q becomes a reference edge exactly once, the maximum number of refraction points due to a change in the reference edge is N. Consequently, the maximum number of refraction points is 3N. N In Algorithm 1, we update the slope of the added area function whenever a convex hull vertex or the reference edge changes. Therefore, we update the slope exactly 3N times even if some of the updating is of 23

no use. We can state the following theorem which gives the time complexity of Algorithm 1. Theorem 5.1 The time complexity of Algorithm 1 is linear in N. 24

Algorithm 1. Find minimum area convex hull 1. Initialization Find the initial configuration of P and Q, and v and v. pr qr Find ec v(eiv^cv rV ). e 4 e.. c 1 Find CHV_A ({CHV},A,vpr r ). Amin Ac, me C e, m v+ vc, mt - 0. nmn c c c c c c Slope_of_added_area_function({CHV},Cb,Cr). 2. Repeat _t - 0. C t - X - X. xr a / {t1} - 0. {txc for each CHV in {CHV} Calculatetxc(CHV,{CHV},S,tr, {txc ). while {t } 0 do xc begin if (t > 0) xr then at - Min{t }. xc xc else at a Max{t }. xc xc Ac Ac + (Cb + CrS)atxc/2. t 4 t + at c min

A. + A, me - e, mv - v, mt t. mmn c c c c c c c Update_slopeCHCHV{CHV} at, C) t < t - at xr xr xc for each CHV in {CHV} Calculate_tc (CHV, {CHV},Sp,tx, {tc} ). end Ac A + (Cb + C S )t /2 t t + t c c xr if (A < A ) then c min A. ~ A,me < e, mv < v, mt < t. min c c c c c c if (e C p) then Find e v (ec,v,v,v ) - c- c c c a c else Find e v c(e,v,vcvp) Stop when e = e. - c i

6. Conclusion We have shown a linear time algorithm for finding the minimal area convex hull for two non-overlapping convex polygons P and Q under translation. This is done by tracing the refraction points of the added area function since the function is piecewise linear and the number of refraction points is linear in N. 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 axis for area, translation and rotation. Because of rotation, the added area function is expected to be sinusoidal when projected. Refraction points becomes refraction curves. If there is linear number of such refraction curves then an algorithm with a lower bound of 0(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. 25

References [1] A. Albano and G. Sapuppo, "Optimal Allocation of Two-Dimensional Irregular Shapes Using Heuristic Search Methods," IEEE Trans. System, Man, and Cybernetics, Vol SMC-10, No. 5, pp. 242248, May 1980. [2] B. Chazelle, "The Bottom-Left Bin-Packing Heuristic: An Efficient Implementation," IEEE Trans. Computers, Vol. C-32, No. 8, pp. 697707, August 1983. [3] H. Freeman and R. Shapira, "Determining the Minimum Area Incasing Rectangle for an Arbitrary Closed Curve," Comm. ACM, Vol. 18, No. 7, pp. 409-413, July 1975. [4] P. C. Gilmore and R. E. Gomory, "Multistage Cutting Stock Problems of Two or More Dimensions," Operations Research, Vol. 13, pp. 94120, 1965. [5] R. Graham and F. Yao, "Finding the Convex Hull of a Simple Polygon," J. of Algorithms, Vol. 4, pp. 324-331, 1983. [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, Vol. 1, No. 2, pp. 169-182, 1982. [8] M. I. Shamos, "Geometric Complexity," Seventh Annual ACM SIGACT Conference, pp. 224-233, May 1975. 26

Appendix. 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.1. If the base edge of the old triangle belongs to P, the area of the new triangle vivjvk is: (vivj x vjvk)/2 1) k ~ k (((Xj, Yj) - (Xi, Yi)) x ((X, Yk) - (Xj, Yj)))/2 I! Expressing X, as (Xk + tx) and Yk as (Yk + SPtx), we have: (((X, Yj) - (Xi Yi)) x (((X + tx),(Yk + St)) - (Xj, Yj)))/2 Expanding the cross product, we have: iY Y. - ) ( - X) (X - X) (Yk - Y ) + (Y - Yi) tx (X - Xi) Sp tx)/2 The sum can be expressed in terms of the area of the old triangle v.v.jv as: ((X - Xi, Y - Y) (Xk - Xj Yk - Yj))/2 + ((Y - Yi) t - (Xj - X ) S t )/2 (v.v. x v.Vk)/2 + ((Xj - X.) Si t - (X. - X ) S t )/2 1) jk j i i x 1 X (viv x Vjk)/2 + (Xj - X.) (S. - S ) tx/2 = area of the old triangle + area change 27

Similarly if the base edge of the old triangle belongs to Q, the I! area of the new triangle v.v.vk can be expressed in terms of the area of vivjvk as: (vjvi X vivk)/2 (vjvi x Vivk)/2 + (Xj - Xi) (Si - ) t/2 Since there are only two kinds of triangles in added area polygons, above results prove the Lemma 3.1. [ 28