A GEOMETRIC APPROACH FOR COMPUTING THE DISTANCE BETWEEN TWO DISKS IN 3-D H. A. ALMOHAMAD* Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117. and Shokri Z. SELIM Department of Systems Engineering King Fahd University of Petroleum and Minerals Dhahran 31261, Saudi Arabia. Technical Report # 94-8 March 1994 Abstract: We consider the problem of computing the distance between two circular disks in three-dimensional space. A geometric approach will be proposed for solving this problem. The approach is based on rotation transformations, projections, and geometric properties of disks. It will be shown that this problem has closed-form solutions for computing the distance and the optimal points. A fast computational algorithm will be proposed. Keywords: Computational geometry, circular disks, distance computation, closed-form solutions. *On Sabbatical Leave from King Fahd University of Petroleum and Minerals, Department of Systems Engineering, Dhahran 31261, Saudi Arabia. 1

I. Introduction The distance problem between two static objects has extensively been studied in the literature. Efficient algorithms have been developed for various types of objects including: line segments [1], boxes [2], polygons [3, 4, 5, and 6], and polytopes [7, 8, 9, 10, and 11]. Other references on the distance and intersection problems can be found in [12 and 13]. In this report, we are interested in computing the distance between two circular disks defined in three-dimensional space with arbitrary position and orientation. The approach for computing the distance depends on the representation used to describe a disk. For example, we can define a disk as a finite number of concentric circles, where each circle is defined by a finite number of points, i.e. discrete disks. In this case, it might be possible to find a polynomial time algorithm for computing the distance between both disks. This method, however, would provide approximate solutions which depend on the number of circles and points used to define a disk. It would require a significant number of iterations to achieve accurate solutions. In this work, we consider a disk as a continuous area of points, i.e. a set of an infinite number of points, where a point can be represented by polar coordinates, Cartesian coordinates, or by some other equivalent parametric representation. Unlike the objects in the previously mentioned problems, which can be described by linear models, the geometry of a disk is nonlinear by nature. In general, distance problems are nonlinear problems, which can be solved using nonlinear mathematical programming methods [14 and 15]. However, the computation time of these methods may not be suitable for real-time applications. In addition, for objects having well defined shapes like disks [16], circles, spheres etc., the special geometric structure of these objects may be used to reduce the complexity of the distance problem and provide fast computational solutions. Our approach for the distance problem between two disks is based on using rotation transformations and geometric properties of disks. The rotation transformations simplify the representation of the problem by eliminating some of the constants from the basic formulation of the distance problem. Using the special structure of the reduced representation and the geometric properties of disks, it will be shown that this problem can be reduced to the problem of computing the distance between a disk and a point. We will show that the latter has closed-form solutions. An algorithm for computing the distance between two disks will be proposed. The proposed algorithm (apparently the first in the literature) requires only a few tests to compute the distance and the optimal points. 2

II. Formulation of the Disks Distance Problem Let F=(X,Y,Z) be the attached coordinates frame of a circular disk K of radius D, centered at the origin 0 and lying in the X-Y plane of F. A disk is a collection of points V which can be represented as follows: K = {V=(Vx,VyVz)T I Vx = r cos(q), Vy = r sin(q), Vz = 0, 0 < r < D} (1) An arbitrary 3D disk is obtained by rotating K and translating its origin with respect to a fixed coordinates frame FO = (XO,YO,Zo). Let R be a 3 x 3 rotation matrix that defines the disk plane, and let P=(Px,PyPz)T be its origin with respect to FO. Let W be the absolute coordinates of a point V on the disk, then K can be defined as follows: K= {W= R V + P IV = (Vx,VyVz)T, Vx = r cos(q), Vy = r sin(q), Vz = 0, 0 < r < D} (2) Let KI and K2 be two disks of radius DI and D2, centered at PI = (Plx, Ply, Piz)T and P2= (P2x, P2y, P2z)T respectively. Let RI = {Rij }, and R2 = {R2ij }, i, j = 1, 2, 3, be the rotation matrices that define the planes of KI and K2 respectively. Determining the distance between KI and K2 is equivalent to solving the following problem: minimize II (R1 V1 + Pl) - (R2 V2 + P2) 112 (3) subject to IIV111<D1, IIV2 II < D2 where Vi = (Vix, Vly, O)T, V2 = (V2x, V2y, O)T, and II 112 denotes the L2-norm. The best way for solving (3) is to find a method that provides closed-form solutions for the distance and the optimal points. In the following, we discuss some of the approaches that we have investigated, and then we develop our geometric approach based on the special properties of the problem under consideration. Problem (3) is a nonlinear optimization problem where both the objective function and the inequality constraints are nonlinear. The above problem has an interesting property about the location of the optimal points that solve (3). We can show that one of the optimal points that minimize the distance between the two disks must be on the border of K1 or K2. This is also true when the disks have some intersection. Therefore, (3) can be reduced to the problem of finding the distance between a disk and a circle. Since the optimal point could be on the border of K1 or K2, one has to compute two distances, and the minimum of these two distances will give the optimum. This approach may lead to closed-form solutions, but as we will see later on, the method we propose is more efficient. Problem (3) can also be viewed as a nonlinear programming problem, where techniques like the KKT (Karush-Khun-Tucker) with Lagragian multipliers [14] may be used. When applied to (3), 3

the KKT produces a system of 10 nonlinear equations in 6 unknowns. Because of the L2-norm and the convexity of disks, the Hessian of the objective function is positive semi-definite. Therefore, the KKT necessary and sufficient conditions are satisfied for the optimality of solutions. This guaranties that any solution of the nonlinear system is a global optimal solution of (3). However, because of the semidefiniteness of the objective function, the solution may not be unique. But this is not of great importance, since we are looking for any pair of points that solve (3). Using the preceding property on the location of optimal points, and the system of nonlinear equations produced by KKT conditions, we have tried to combine these equations and to use induction and/or deduction procedures to find out closed-form solutions for the distance problem. With this formulation, one has to solve three problems, where each problem is described by a subset of nonlinear equations. The first two problems are based on the assumption that one of the optimal points is on the border of the first disk, and the other is interior to the second disk, and vice-versa. These two problems are equivalent to the distance problem between a circle and a disk. We can show that the KKT approach provides closed-form solutions for the distance between a disk and a circle. However, we failed to find closed-form solutions for the third problem, where both optimal points are assumed to be on the borders of the disks, i.e. distance problem between two circles. In this case, we found a system of 8 nonlinear equations in 6 unknowns, which does not apparently have a direct closed-form solution. The approach we propose here is, instead, purely geometric. First, we show that using some rotation transformations the formulation of the distance problem (3) can be reduced to a simpler one. Second, using projections and the particular geometry of disks, we show that this problem can be transformed into a problem of computing the distance between a point and a disk. The latter has closed-form solutions. This geometric approach is developed in Sections III and IV. III. Geometric Transformations Our approach for the distance problem consists first of using rotation transformations to reduce (3) to a simpler form. For this, recall that a rotation matrix R is an orthogonal matrix satisfying R RT = RT R = I, where RT denotes the transpose of R, and I is a 3 x 3 identity matrix. Let p be a three-dimensional vector defined as follows: p = R1 V1 +P1 - (R2V2 + P2) (4) Multiplying both sides of (4) by RT, one obtains after rearrangement: R1 p = V1- RT R2 V2 - R1 (P2-P1) (5) 4

Let OP= R1 (P - P), and OR= RTR2, then (5) becomes: R p = V1 - ORV2 - OP (6) Since II R p 112 = II p 112, the distance problem (3) becomes: minimize IIV1 - ( R V2 + 0P) 112 (7) subject to IIVi II < D1, IIV2 II < D2 With the above transformation, (7) is the problem of finding the distance between a disk K1 lying in the (XO,Yo) plane and centered at the origin Oo of the fixed coordinates frame Fo, and a disk K2 of center ~P and rotation matrix OR. Further reductions can be applied on OR to make the X-axis of the frame attached to disk K2 parallel to the Xo-axis of the fixed frame FO. This means that OR can be reduced to a rotation matrix that rotates the plane of K2 about the Xo-axis only. For this, we shall show that for any given matrix OR, there exist three rotation matrices A, B, and R such that: B R AT = R (8) where A, B, and R are of the forms: cos~ ) -sin(c) 0 cos(3) -sin(f) 0 1 0 0 1 A = sin(a) cos(a) 0, B= sin(P) cos(p) 0 R = 0 cos(y) -sin(y) - 0 0 1 L 0 0 1 0 sin(y) cos(y) The proof for relation (8) is conducted as follows: let C be a 3 x 3 rotation matrix such that C = OR AT. Post-multiply OR by AT and set the entry C31 to zero, we obtain: C31 = OR31 cos(a) - OR32 sin(a) = 0 where ac can be computed as follows: tan (a) oR3 o = atan (R31) (9) The value of ca can be computed in [0, 2i:] by checking the signs of 0R31 and 0R32. Since the disk is assumed to have two identical sides, the solutions ca + i: and a - t: correspond to the 5

same plane of the disk. Thus, we can restrict a to be in [0, tn]. Note that, if OR32 = 0, then we can permute column 1 and 2 of OR so that the entry C31 = 0. In this case, the permutation matrix is obtained by setting a = - /2 in A. Thus, the resulting matrix C is of the form: -CII C 12 C13C= C21 C22 C23 0 C32 C33 Let D be a 3 x 3 rotation matrix such that D = B C. Post-multiply C by B and set the entry D21 to zero, we obtain: D21 = Cl sin(P) + C21 cos(3) = 0 which implies that: tan (3) - C21 = = -atan (21) (10) As in the case of oa, the solution 3 can be computed in [0, 7t]. If CII = 0, then we can permute rows 1 and 2 of C so that the entry D21 = 0. The resulting matrix D is of the form: -Dll D12 D13D= 0 D22 D23 0 D32 D33 Since D is an orthonormal matrix, then D 1 must be equal to 1 or -1, and D12 = D13 = O. If D = -1, then we can pre-multiply D by a matrix Ii such that R = Ii D, where II is of the form: — 1 0 0O 1 0 D- 0 0D3 In this case, we have RI = 1. Since D is a rotation matrix, we have D22 = D33, and D23 = -D32. Therefore, by setting D22 = cos(y) and D23 = -sin(y), the matrix R will be of the form: 1 0 0 R = O cos(y) -sin(y) (11) 0_ sin(y) cos(y) where R = D, if DI 1= 1, or R = I D, if D 11 = -1, and y is determined in [0, tR] by checking the signs of D22 and D23. Finally, the above transformations reduce OR, to a rotation matrix R that 6

rotates the plane of disk K2 with an angle y about the Xo-axis of the fixed frame Fo. Relation (8) is proved. Consider now the objective function IIVI - (0R V2 + 0P)112 of (7). Pre-multiply the expression inside the norm by B and post-multiply OR by AT A, we obtain: 1IIV - (0RV2 + P) 112 = IBV V - BORAT A V2 - B P 112 since the L2-norm is invariant under rotation. Let M = B V1, V = A V2, and P = B ~P, and substitute R for B OR AT in the above equation, we have: II VI - (OR V2 + OP) 112 = II M - (R V + P) 112 where: M = (ri cos(ql+ 3), ri sin(ql+ P), O)T, V = (r2 cos(q2+ a), r2 sin(q2+ ), O)T, and P = (Px, Py, Pz)T. Replacing q + P by 01 in M, and q2+ a by 02 in V, we have: M = (ri cos(01), rl sin(01), O)T, 01 = qi+ P = (Mx, My, O)T (12) and, V = (r2 cos(02), r2 sin(02), O)T,02 = q2+ ao = (Vx, Vy, )T Finally, (7) is reduced to the following equivalent problem: minimize II M - ( R V + P) 112 (13) subject to IIMII < DI, IIVII < D2 where disk KI is lying in the (Xo,Yo) plane and centered at Oo, and disk K2 is lying in the plane defined by the rotation matrix R and centered at point P = (PxPyPz)T. Note that, in the above formulation, the X-axis of the frame attached to K2 is parallel to the Xo-axis of the fixed coordinates frame Fo, and R is a matrix that rotates K2 by an angle y about Xo-axis. As we can see, the above rotations have no effect on the distance problem. They only change the phases of the optimal points, which can be restituted later by applying the inverse rotation transformations on the obtained solutions. Because of the reduced structure of R, the above formulation provides an optimal representation of the distance problem between two disks. Additional geometric transformations can be applied on the objective function of (13), to produce various possible configurations of the two disks in space. But the solution complexity of the resulting problems will be equivalent to that of (13). 7

IV. Geometric Properties In this section, we show that the distance problem between two disks can be reduced to the problem of computing the distance between a disk and a fixed point. For this, we first proceed by presenting some preliminary results for computing the distance between a disk and a point. Using the reduced formulation (13), we give in Proposition 1 a procedure for computing the distance between disk K1 and a fixed point in 3D. Proposition 2 gives a similar procedure for computing the distance between disk K2 and the origin Oo. Both procedures provide closed-form solutions for the problems under consideration. Proposition 1: Let W=(Wx,Wy,Wz)T be a point in three-dimensional space (Fig. 1), and let IIWIIxy denote the distance between the origin O and the projection of W on the (XO,Yo) plane. Let d(M,W) = II M - W 112 denote the distance between a point M E KI and W. Then, there exists an optimal point M = (Mx, My, O)T that minimizes the distance between KI and W such that: min d(M,W) = d (M,W) MEK1 * * The minimum distance d(M,W) and the coordinates of the optimal point M depend on the following two cases: * 2 2 * DI Wx * DI W D Case 1: If IIWIIxy > Di, then d(M,W) = (IIWIIxy - D)2 + Wz, Mx = IIWlx and My -= WY'~M,- Illy liWllxy * 2 * * Case 2: If 0 < IIWIIxy < D1, then d(M,W) = Wz, Mx = Wx, and My = Wy. Proof: From simple geometry, we can see that if IIWIIxy > D1, which implies that W is outside the disk, then the optimal point M* is the intersection point between the border of KI and the line joining the projection of W on the (Xo,Yo) plane with the origin 00. The proofs for the other two cases are straightforward. Proposition 1 is proved. Several remarks are to be considered for the geometric interpretation of Proposition 1 (Fig. 1). First, we can easily see that if IIWIIxy > DI, then W is outside the disk. In this case, the nearest point M* to W is the point that intersects the boundary of KI with the line joining the projection of W and the prigin of the disk. Thus, the distance decreases when W gets closer to M*. This means also that the closer W is to the origin Oo of the disk, the less the distance between W and the disk is. 8

Zo W T K1 Yo M* \ I I Fig. 1- Minimum distance between a fixed point W and disk K1. This remark shows also that, if W belongs to disk K2, which is assumed here to be completely outside K1, then the minimum distance between K2 and K1 can be obtained by computing the minimum distance between K2 and the origin of K1. As we can see from both cases of Proposition 1, the distance d(M*, W) depends only on the location of W with respect to the origin O0, and it is independent of the location of the optimum point M*. Second, the minimum distance between KI and W is either the distance between W and a point on the border of K1 (IIWIIxy > D1), or the distance between W and the plane of K1 (0 < IIWKly < D1). Third, a necessary and sufficient condition for the intersection between K1 and K2 at W is that W be in the (Xo,Yo) plane (Wz = 0) and its projection is inside the disk K1 (0 < IIWIIxy < D1). Fourth, because of the symmetry of a disk, the optimal point M* may not be unique. Therefore, there may also exist a point W' of K2 that gives the same distance. However, this is not of great importance, since we are looking for any pair of points of KI and K2 that minimize the distance. These remarks are valid for any point W in the space, in particular, for the optimal point of K2 that minimizes the distance between KI and K2. The main result from the above remarks is that the optimal point of K2 that minimizes the distance between K1 and K2 is the point that minimizes the distance between K2 and the origin Oo of KI. This result is true for both cases of Proposition 1. Since the objective function of (13) is symmetric, in the sense that we can move K2 to the origin of KI and vice-versa (by pre-multiplying the objective function by RT), the above remarks are also valid when K2 lies in the (Xo,Yo) plane and centered at the origin Oo, and W is a point of K1. Therefore, it is necessary to compute also the optimal point of K1 that minimizes the distance between K1 and the origin of K2. 9

Thus, the distance between the two disks can be determined by computing the nearest point of disk K2 to the center of K1, and the nearest point of K to the center of K2. The minimum of these two distances will give the first optimal point for the distance problem. This optimal point will then be used to determine the second optimal point of the of the other disk. Thus, the distance between KI and K2 can be computed in two steps, where in each step a point-disk distance is to be evaluated. Proposition 2 gives a procedure for computing the distance between K2 and the origin Oo of K1. Proposition 2: Let W = R V+ P be a point of K2, and let d(Oo,W) = IIR V+ Pl12 denote the distance between W and O. Then, there exists an optimal point W = (W, Wy, Wz)T = R V + P that minimizes the distance between K2 and O such that: min d(O0,W) = d(Oo,W*) WeK2 Depending on the following two cases, the minimum distance d(Oo,W*) and the optimal point V* are: Case 1: If IIRT Pllxy > D2, then d(Oo,W*) = (IIRT Pllxy - D2)2 + (RT P)Z, *_ D2(RTP)x * D2(RT P)y V =- D 2RTPI)X, and Vy =-a x IIRT Pllxy'y IIRT Plxy Case 2: If 0 < IIRT PlIxy < D2, then d(Oo,W*) = (RT P)2, Vx = - (RT P)x, and Vy= - (RT P)y. where IIRT Pllxy is the distance between the projection of point (RT P) on the (Xo,Yo) plane and the origin Oo, and (RT P)x, (RT P)y, and (RT P)z are the absolute coordinates of (RT P). Proof: The distance between a point W = R V+ P and the origin Oo is as follows: d(Oo,W)= IIWI12 = IIR V + P 112 Since the L2-norm is invariant under rotation, we have: d(Oo,W) = II V+ RT P 112 where K2 is lying in the (Xo,Yo) plane and centered at the origin Oo, and RT P is a fixed point in three-dimensional space (Fig. 2). 10

Zo 1 I~~RTp K2 I xo Fig. 2- Computing the minimum distance between K2 at center P and the origin OO. The problem is equivalent to computing the minimum distance between K2 at center 00 and the point RT P. Thus, we can use Proposition 1 to compute the minimum of d and the optimal point V*. For this, let IIRT Pllxy denote the distance between QO and the projection of RT P on the (Xo,Yo) plane. From Proposition 1, there exists an optimum point V = (Vx, Vy, O)T e K2 that minimizes the distance between K2 and RT P, that is: If IIRT Pllxy > D2, then d(Oo,W*) = (IIRT PlIxy - D2)2 + (RT P)2, and * _ D2(RT P)x * D2(RT P) x IIRT PIIxy' IIRT PlIIxy If 0 < IIRT Pllxy < D2, then d(Oo,W*) = (RT Pi Vx = - (RT P)x, and Vy = - (RT P)y. For both cases, W* can be computed from the relation W* = R V* + P. Proposition 2 is proved. Consider now problem (13), that is: minimize II M - ( R V+ P) 112 subject to IIMII < DI, IIVII < D2 Let d(Oo, W0 ) be the distance between Oo and Wo, where W0 is the optimal point of K2 that * * minimizes the distance between O and K2. Let d(4, P) be the distance between M p and P, where Mp is the optimal point of K1 that minimizes the distance between K1 and P. Then we have the following Lemma: 11

Lemma 1: The distance between KI and K2 is as follows: d(Mo,Wo) if d(Oo,Wo) < d(Mp, P) min min d(M,W) = d(Mp,Wp) if d(Oo,Wo) > d(Mp, P) WeK2 MeK1 where W0 is the nearest point of K2 to the origin Oo, M is the nearest point of KI to W 0, Mp is the nearest point of K1 to the center P of K2, and Wp is the nearest point of K2 to Mp. The distances d(Mo, W0) and d(Mp, Wp), and the corresponding optimal points can be computed from Propositions 1 and 2. Proof: Let WO be the nearest point of K2 to the origin Oo of K1 (see Fig. 3). W0 can be computed from Proposition 2, we have: min d(O0,W) = d(O,Wo ) WEK2 Since WO is known, we can compute the nearest point Mo of K1 to W0. Proposition 1 gives: min d(M,W0) = d(Mo,Wo) Me K Similarly, let Mp be the nearest point of K1 to the origin P of K2, then from Proposition 1, we have: min d(M,P) = d(Mp, P) MeK1 The nearest point Wp of K2 to Mp can be computed by using Proposition 2 (see fig. 4), we obtain: min d(Mp,W) = d(Mp, Wp) W K2 Assume first that d(Oo,Wo) < d(Mp,P). This means that WO is closer to Oo than Mp to P is. Since Wo is the closest point of K2 to the origin Oo of K1, then Wo is the closest point to disk K1. This is true because the minimum distance between a disk and a fixed point depends only on the location of the fixed point in space, or equivalently, the minimum distance depends on the distance between the point and the center of the disk. Consequently, from Proposition 1, there 12

exists an optimal point Mo of KI, that is the closest point to Wo. It follows that the points MO and WO are the optimal points that minimize the distance between both disks. This implies that d(MWo) < d(Mp,W) and consequently we have: * * min min d(M,W) = d(Mo,Wo) WeK2 MeKi For the case where d(Oo,W0 ) > d(Mp,P), symmetric arguments can be used to show that Mp and * Wp are the optimal points that satisfy the minimum distance between K1 and K2. Lemma 1 is proved. K2 | Kl d( Wo~~* Il KI — o- 1 /I Fig. 3- Determining the optimal points M0 and WI. 13 13

V. Algorithm: The first two steps of the algorithm consist of computing the distances d(Oo,Wo) and d(Mp,P). The distance between the two disks and the coordinates of the optimal points are computed in Steps 3 or 4. Step 1: Using Proposition 2, compute the distance between the origin O and disk K2. This gives * * * d(Oo,Wo) and the coordinates of the optimal point V0 E K2. Compute W0 from the relation W0 = R Vo +P. Step 2: Using Proposition 1, compute the distance between disk K and the center P of K2. This * * gives d(Mp,P) and the coordinates of the optimal point Mp E K1. Step 3: If d(Oo,Wo) < d(Mp,P), then use Proposition 1 for determining the distance between Wo* and disk K1. This gives the distance between the two disks d(Mo,Wo), and the coordinates of the optimal point Mo* of K1. End. Step 4: If d(Oo,Wo) > d(Mp,P), then use Proposition 2 for computing the distance between Mp and disk K2, that is, compute the minimum of IIV - RT(Mp - P)112. This gives the distance between the two disks d(Mp,Wp), and the coordinates of the optimal point Wp of K2. End. Note that, Steps 1 and 2 require two comparison tests to find the distances d(Oo,Wo) and d(Mp,P). Steps 3 or 4 require 1 test for comparing both distances and two other tests to find the minimum distance between the two disks. Therefore, the algorithm terminates by finding the closed-form solutions of the distance and the optimal points in at most 5 comparison tests. Appendix A gives the detailed computational procedures for the algorithm. For all cases, we obtain simple expressions for the closed-form solutions, which can easily be computed with only a few operations. V. Conclusion: In this technical report, we presented an efficient algorithm for computing the distance between two circular disks in 3D. Some rotation transformations were used in Section 3 to simplify the formulation of the initial problem. These transformations may not be required for developing the algorithm. One may apply directly the proposed algorithm on the formulation given in (7). It was 14

shown that the distance problem is reducible to a two-step problem, where each step involves the computation of the distance between a disk and a fixed point in space. Closed-form solutions were obtained for the point-disk distance problem. An algorithm that requires about 5 comparison tests was proposed. The algorithm provides closed-form solutions for the distance between two disks and the optimal points. Acknowledgments: The authors would like to thank the Research Committee at King Fahd University of Petroleum and Minerals for its support to conduct and accomplish this work. Thanks are also extended to The Department of Industrial and Operations Engineering at the University of Michigan, Ann Arbor, where the first author is currently on Sabbatical Leave. In particular, we would like to thank S. 0. Duffuaa and K. G. Murty for their helpful comments and fruitful discussions. 15

Appendix A Detailed Computations of the distance algorithm between two disks: Step 1: Computing d(Oo,Wo) from Proposition 2: (11RT PlIxy - D1)2 + (RT p)2 if IIRT Pllxy > D1 * Z d(Oo,Wo) = (RT p)2 if 0 < IIRT PIIxy < D Step 2: Computing d(Mp, P) from Proposition 1: (IP IIxy -D2)2+ P2 if lip IIxy > D2 d(Mp, P) = P2 if 0 < lIP lixy < D2 At this stage of the algorithm, we assume that both distances d(Oo,Wo) and d(Mp, P) are known. Step 3: If d(Oo,Wo) < d(Mp, P), then from Proposition 2, the coordinates of the optimal point V 0 e K2 are as follows: D2 (RT P)x D2 (RTP), and W = R Case 1: If IIRT Plly > D2, then V - IRT ll - IIRT PIIxnd W R VO + P. Using proposition 1, the minimum distance d(Mo,WO) and the coordinates of the optimal point Mo E K1 depend on the following cases: ~ * *_ 2 Case 1.1: If IIW0 lKxy > D1, then d(M0,o) = (IIW lxy - D)2 + (W0)z D1 W0x D1 WOy MOx =,and My = IIWo llxy IIWollxy * Case 1.2: IfO I IIWO lIxy < D1, then d(M,Wo) = (W0)z, Mox = WTx, and MOx = WOy. Case 2: If 0 < IIRT Pllxy < D2, then V0x = - (RT P)x,V0y = - (RT P)y, the distance d(M0,W0) and the coordinates of M0 are: Case 2.1: If IIWo llxy > D1, then d(M0,Wo) = (llWo llxy - D1)2 + (W)z 16

Di Wo, D1 Woy Mox =,and Moy = IIWo lixy IIWOllxy Case 2.2: If 0 < IIWo llxy < DI, then d(M0,WO) = (W0)z, Mo = Wo, and * * Moy = Wy. Step 4: If d(Oo,Wo) > d(Mp, P), then using Proposition 2, the coordinates of the optimal point Mp E K1 depend on the following cases: DI Px * D1 Py and d(Mp, * Case 1: If lIIP lxy > D1, then My -= IP i, and d(Mp, Wp) is as follows: Case 1.1: If IIRT(Mp - P)llxy > D2, then d(Mp,Wp) = (IIRT(Mp - P)llxy - D2)2 + (RT(Mp -P))2 and the coordinates of the optimal point Vp are: D2 (RT(Mp - P))x, D2 (RT(M* - P))y Vpx =, and Vpy- IIRT(Mp-P)llxy IIRT(Mp-P)llxy Case 1.2: If 0 < IIRT(Mp - P)llxy < D2, then d(M;, Wp) = (RT(Mp P)) Mpx = (RT(Mp - P))x, and Mpy = (RT(Mp - P))y Case 2: If O < IIP llxy < D1, then Mpx = Px, Mpy = Py, and d(Mp,Wp) is as follows: Case 2.1: If IIRT(Mp - P)llxy > D2, then d(Mp, Wp) = (IIRT(Mp - P)llxy - D1)2 + (RT(Mp - P))z2 and the coordinates of the optimal point Vp are: D2 (RT(Mp- P))x * D2 (RT(Mp- P))y Vpx = ~, and Vpy = IIRT(Mp - P)llxy IIRT(Mp - P)llxy Case 2.2: If O < IIRT(Mp - P)llxy < D, then d(Mp,Wp) = (RT(Mp - ))2 Vpx = (RT(M - P))x, and Vpy = (RT(M - P))y 17

REFERENCES: [1] V. Lumelsky, On the computation of distance between line segments, Inform. Process. Lett. 21 (1985), 55-61. [2] W. Meyer, Distance between boxes: Applications to collision detection and clipping, IEEE Inter. Conf. on Robotics and Automation (1986), 597-602. [3] D. Davis and G. T. Toussaint, An optimal algorithm for determining the visibility of a polygon from an edge, IEEE Trans. on Computers C-30 (1981). [4] J. T. Schwartz, Finding the minimum distance between two convex polygons, Inform. Process. Lett. 13 (1981), 168-170. [5] B. K. Battacharya and G. T. Toussaint, Efficient algorithm for computing maximum distance between two finite planar sets, J. Algorithms 4 (1983), 121-126. [6] T. Asano, L. Guibas, J. Hershberger, and H. Imai, Visibility of dijoint polygons, Algorithimica 1 (1986), 49-63. [7] M. Sharir and A. Baltsan, On shortest paths amidst convex polyhedra, SIAM J. Comput. 11 (1987), 561-572. [8] P. Wolfe, Finding the nearest point in a polytope, Math. Prog. 11 (1976), 128-149. [9] M. Orlowski, The computation of the distance between polyhedra in 3-space, SIAM Conf. on Geom. Modl. and Robotics (1985). [10] E. G. Gilbert, D. W. Johson, and S. S. Keerthi, "A fast procedure for computing the distance between complex objects in three-dimensional space", IEEE Trans. on Robotics and Automation 4-2 (1988), 193-203. [11] J. E. Bobrow, "A direct minimization approach for obtaining the distance between convex polyhedra", Inter. Journal of Robotics Research, 8-3 (1989), 65-76. [12] D. T. Lee and F P. Preperata, "Computational geometry - A survey", IEEE Trans. on Computers, C-33-12 (1984), 1072-1101. [13] J. O'Rourke, Computational geometry, Ann. Rev. Comput. Sci. 3 (1988), 389-411. [14] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming, Theory and Algorithms, Second Edition, John Wiley and Sons Inc., 1993. [15] D. G. Luenberger, "Optimization by vector space methods", John Wiley & Sons Inc., 1969. [16] H. A. Almohamad, and S. Z. Selim, "Closed-form solutions for computing the intersection between two circular disks in 3D", Tech. Report # 94-7 (1994), Univ. of Michigan, Ann Arbor, Dept. of Indusrial and Operations Engineering. [17] H. Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag, 1987. [18] K. Melhorm, Multi-dimensional searching and computational geometry, SpringerVerlag, i984. [19] F. P. Preparata and M I. Shamos, An introduction to computational geometry, Springerverlag, 1985. [20] J. A. Humel, Vector Geometry, Textbook, Addison-Wesley Publishing Co. Inc., 1965. 18

[21] P. A. White, Vector Analytic Geometry, Textbook, Dickenson Publishing Co. Inc., Belmont, California, 1965. 19