From: Cassiano Durand Newsgroups: sci.math.num-analysis,sci.math.research Subject: Family of lines tangent to 3 gives spheres Date: Fri, 12 Sep 1997 18:29:32 -0500 Hi Everybody, How can we describe parametrically the family of lines simultaneously tangent to 3 given spheres (radii and center coordinates are known)? Regards Cassiano Durand ============================================================================== From: rusin@math.niu.edu (Dave Rusin) Newsgroups: sci.math.num-analysis,sci.math.research,sci.math.symbolic Subject: Re: Family of lines tangent to 3 gives spheres Date: 22 Sep 1997 22:31:56 GMT This is in response to a request of Cassiano Durand , who wrote: >How can we describe parametrically the family of >lines simultaneously tangent to 3 given spheres (radii >and center coordinates are known)? I can express this family as an algebraic variety, but it gets rather messy when we try to get close to a parameterization. Any line contains a vector v of length 1 (unique up to negation); the plane perpendicular to v meets the line in a unique point P. So we may parameterize the set of all lines in R^3 in a 2-to-1 way as the variety of pairs (v,P) defined by the vanishing of the polynomials v1^2 + v2^2 + v3^2 - 1 p3*v3 + p1*v1 + p2*v2 The points on the line indexed by (v,P) are the points of the form P + t v, for t in R. A line is tangent to a sphere if its closest approach to the center C is at a distance equal to the radius R of the circle. Well, the point Q of closest approach is the one at which the vector Q-C is perpendicular to v. From 0 = < v, Q-C > we deduce t= -, so the point is P - v. This point's distance from the center is the square root of || ( P - v ) - C ||^2 = ||P-C||^2 - ^2, so the conditions of tangency are stated ||P-C||^2 - ^2 = R^2. As I'll explain in a moment, these equations become complicated, so let us switch to a more canonical representation of the situation. Rotating and scaling as necessary, we may assume one sphere is of radius 1 at the origin, another is of radius r centered at (a,0,0), and the third is of radius s centered at (b, c, 0). Then the three equations for tangency become the vanishing of p1^2+p2^2+p3^2 - 1 p1^2+p2^2+p3^2-2*a*p1+a^2 -a^2*v1^2 - r^2 p1^2+p2^2+p3^2-2*b*p1-2*c*p2+b^2+c^2 -(b*v1+c*v2)^2 - s^2 since =0. Five equations in 6 unknowns determine, in general, a curve. This curve can be parameterized e.g. by arclength. Of course there are degenerate cases, not the least significant of which is that this intersection will be empty if the three spheres aren't more or less in a line (i.e. if |c| is large relative to a, b, r, and s.) I don't know how much more explicit a parameterization you want. If you're looking for a numerical method, you could hope for at least one member of the family to be known, then vary (say) p1 and use Newton's method to compute the new values of p2, p3, v1, v2, and v3. Of course this will fail near critical points of the coordinate function p1. Alternatively, we can try to handle the general situation from the perspective of algebraic geometry; I can't get too far. Let us see if we can visualize this curve in R^6. First simplify the set of equations a bit; they're equivalent to the vanishing of p1^2+p2^2+p3^2-1 v1^2+v2^2+v3^2-1 p3*v3+p1*v1+p2*v2 R-2*a*p1 -a^2*v1^2 S-2*b*p1-2*c*p2 -(b*v1+c*v2)^2 where R=1+a^2-r^2, S=1+b^2+c^2-s^2. From the first equation (or from a look at the geometry) P will be on the unit sphere. It's of interest to find the possible P; these are the points to stand at on the first sphere if one wants to be able to draw a line tangent to the two other spheres. The set of these P should also be a curve (i.e., it's the image of the curve in R^6 under the projection (v,P) -> P ), and a parameterization of this curve will more or less produce a parameterization of the original curve, using the five equations to compute v from P. Actually it's easy to eliminate v1 and v2 from the equations; they're rational functions of P and a, b, c, R, S, and v3. This leaves only the equations || P || = 1 and two quartic polynomials in v3. (This reduction will miss the points on the original curve which happen to have v3=0 or some p_i=0, since these appear in the denominators of the expressions for v1 and v2. For similar reasons we must assume a isn't zero, i.e., the second sphere must be distinct from the first!) Those quartic polynomials are however actually quadratics in V=v3^2; indeed, the products v1v3 and v2v3 also depend only on V. This is to be expected, since there is a 2-fold ambiguity in the selection of the vector v in the first place. Expressing the remaining polynomials as quadratics in V makes it easy to manually eliminate v3, too. Again ignoring those points on the original curve which make a denominator equal to zero, we may deduce a polynomial in a, b, c, R, S, and the coordinates of P whose vanishing determines a surface in R^3; this surface, intersected with the unit sphere, determines our curve in R^3. Maple informs me this polynomial has 2844(!) terms. However, it factors into (p2^2+p3^2)^2 and two polynomials of degree 6 in the coordinates of P. Obviously the real zero-locus of the first factor consists only of the points +-(1,0,0) since we have || P || = 1. The other two polynomials have 129 terms each. They may be written as f1+f2 and f1-f2 where, if I haven't mistyped, f1= -16*c^3*a^3*p1^3*p2^3+8*c^3*a^2*R*p1^2*p2^3+2*c^4*R^2*p1^4+16*b^4*a^2*p1^2*p2 ^2*p3^2+8*b^4*a^2*p1^2*p2^4+8*b^4*a^2*p1^2*p3^4+16*c^4*a^2*p1^4*p3^2+16*c^3*a^3 *p1^3*p2*p3^2-4*a^4*S*c^2*p3^4-16*a*R*c^2*b^2*p1*p3^4+4*a^2*R*S*c^2*p2^2*p3^2+ 16*a^2*p1^2*c^2*b^2*p3^4+8*a^4*b*p1*c^2*p2^2*p3^2-16*a^3*b^3*p1^2*p2^4-16*a^3*b ^3*p1^2*p3^4-32*a^3*b^3*p1^2*p2^2*p3^2-8*a^3*p1*S*c^2*p2^2*p3^2+16*a^3*p1^2*b*c ^2*p2^2*p3^2-8*a^2*R*b*p1*c^2*p2^2*p3^2+16*a^2*p1^2*c^2*b^2*p2^2*p3^2-16*a*R*c^ 2*b^2*p1*p2^2*p3^2+8*a^3*c^2*b^2*p1*p2^2*p3^2+4*c^2*b^2*R^2*p2^2*p3^2-8*a^2*R*b *p1*c^2*p3^4+16*a^4*c^2*p2^4*p3^2+8*a^4*c^2*p2^2*p3^4-4*a^4*S*c^2*p2^2*p3^2+8*a ^4*c^2*p2^6-4*a^2*c^2*b^2*R*p2^2*p3^2-4*a^2*c^4*R*p3^4-8*a^3*p1*S*c^2*p3^4+16*a ^3*p1^2*b*c^2*p3^4+2*c^4*R^2*p3^4+2*b^4*R^2*p3^4+8*a^4*b*p1*c^2*p3^4+8*a^4*b^2* p1^2*p2^4+8*a^4*b^2*p1^2*p3^4+4*a^2*R*S*c^2*p3^4+16*a^4*b^2*p1^2*p2^2*p3^2+16*a ^3*S*b^2*p1*p2^2*p3^2+8*a^3*S*b^2*p1*p3^4+8*a^3*S*b^2*p1*p2^4+8*a^2*b^3*p1*R*p2 ^4+8*a^2*b^3*p1*R*p3^4+16*a^2*b^3*p1*R*p2^2*p3^2+8*a^3*c^4*p1*p3^4-8*a^2*S*b^2* R*p2^2*p3^2-4*a^2*S*b^2*R*p2^4-4*a^2*S*b^2*R*p3^4+4*c^2*b^2*R^2*p3^4+8*a^3*c^2* b^2*p1*p3^4-4*a^2*c^2*b^2*R*p3^4+8*a^2*p1^2*c^4*p3^4-8*a*R*c^4*p1*p3^4+2*a^4*S^ 2*p3^4+2*a^4*c^4*p3^4+16*a^3*p1*c^3*p2^3*p3^2+16*a^3*p1*c^3*p2*p3^4+8*c^4*a^3* p1^3*p3^2-8*a^4*S*b*p1*p3^4-8*a^4*S*b*p1*p2^4-16*a^4*S*b*p1*p2^2*p3^2-16*b^4*R* a*p1*p2^2*p3^2-8*b^4*R*a*p1*p2^4-8*b^4*R*a*p1*p3^4-16*c^2*b^2*a*R*p1^3*p3^2+4*a ^2*R*S*c^2*p1^2*p3^2-8*c^2*b*a^2*R*p1^3*p3^2+16*b^2*a^2*c^2*p1^4*p3^2+4*c^2*b^2 *R^2*p1^2*p3^2+4*b^4*R^2*p2^2*p3^2-16*c^4*a*R*p1^3*p3^2-4*a^2*c^4*R*p1^2*p3^2-8 *c^2*S*a^3*p1^3*p3^2+16*c^2*b*a^3*p1^4*p3^2+2*b^4*R^2*p2^4-8*a^2*R*c^3*p2*p3^4+ 8*a^4*c^3*p2*p3^4+8*a^4*c^3*p2^3*p3^2+16*a^4*b*p1*c*p2^5+32*a^4*b*p1*c*p2^3*p3^ 2+16*a^4*b*p1*c*p2*p3^4+8*a^2*c*p2^5*b^2*R+8*a^2*c*p2*b^2*R*p3^4+16*a^2*c*p2^3* b^2*R*p3^2+4*a^4*S^2*p2^2*p3^2-16*a^3*c*p2^5*b^2*p1-16*a^3*c*p2*b^2*p1*p3^4-32* a^3*c*p2^3*b^2*p1*p3^2+2*a^4*S^2*p2^4-8*c^3*a^2*R*p2^3*p3^2+4*c^4*R^2*p1^2*p3^2 -8*c^3*a^2*R*p1^2*p2*p3^2-8*a^4*S*c*p2^5-8*a^4*S*c*p2*p3^4-16*a^4*S*c*p2^3*p3^2 -8*c^4*a*R*p1^5+8*c^4*a^2*p1^6+48*b^2*a^2*c^2*p1^4*p2^2+12*c^2*b^2*R^2*p1^2*p2^ 2+8*c^2*b*a^2*R*p1^3*p2^2+8*c^2*S*a^3*p1^3*p2^2-48*c^2*b^2*a*R*p1^3*p2^2-4*a^2* R*S*c^2*p1^2*p2^2-16*c^2*b*a^3*p1^4*p2^2 (105 terms) and f2= -8*p2*p1*b*c*(2*a*p1-R)*(-2*c^2*a*p1^3+R*c^2*p1^2+2*p1*a^2*b*p3^2+2*p1*a^2*b* p2^2-2*p1*a*c^2*p3^2-2*p1*a*b^2*p3^2-2*p1*a*p2^2*b^2-a^2*c^2*p3^2+2*a^2*c*p2^3+ 2*a^2*c*p2*p3^2-a^2*S*p3^2-a^2*p2^2*S+p3^2*R*c^2+b^2*R*p3^2+b^2*p2^2*R) (26 terms when expanded) So we conclude that the locus of lines touching the three spheres, less a (presumably proper) subvariety, is the union of two curves, each the intersection of the unit sphere with a surface of degree 6. It would be incredible lucky for this curve to have genus zero, that is, to allow a parameterization by rational functions. Assuming the curve is of higher genus, it's not particularly clear that a parameterization by e.g. elliptic functions is at all helpful. But at least this gives an alternative method of parameterization: a typical line may be obtained by selecting an arbitrary pair (p1, p2) in the unit disc computing p3 as the root of one of two quartics in p3 computing V as a rational expression in the other parameters selecting either v3=sqrt(V) computing v1, v2 as rational functions in everything else. If at any stage only non-real value are obtained, the pair (p1,p2) must be rejected. I suppose something like a Sturm sequence could be used to decide in advance the region of pairs (p1,p2) which will allow a real root in each further calculation. As noted in the previous discussion, this method will miss some of the lines, but those may be found in a similar way (e.g. in the original 5 equations set p1=0 at the beginning, then eliminate v1, v2, v3 and solve for p3, etc., as before). In any application I could imagine, it would make sense to encode the parameterization not as an explicit set of functions but rather as a set of elimination procedures, suitably programmed to trap for zero denominators and so on; the explicit formulae are just too complicated. dave (I've added sci.math.symbolic to the Newsgroups: line, since it seems clear that finding a "nice" answer to this question will involve heavy use of symbolic engines.) ============================================================================== From: dch@ecs.ox.ac.uk (David Handscomb) Newsgroups: sci.math.num-analysis,sci.math.research Subject: Re: Family of lines tangent to 3 gives spheres Date: 23 Sep 1997 11:56:50 GMT In article <3419D05C.3822@alcor.cs.purdue.edu>, Cassiano Durand wrote: >Hi Everybody, > >How can we describe parametrically the family of >lines simultaneously tangent to 3 given spheres (radii >and center coordinates are known)? > >Regards >Cassiano Durand > I do not know whether your problem has already been solved or published. An approach that suggest itself is the following. The common tangents to two spheres are the generators of a one-parameter family (call the parameter Alpha) of circular-section hyperboloids of one sheet, with a common axis containing the centres of the two spheres. (This family includes two limiting elements corresponding to the extremes of the valid range of Alpha: if the two spheres do not intersect then there are two tangent circular cones; if they do intersect then there is one tangent cone and there is also the set of tangents to their circle of intersection.) The third sphere may or may not then intersect some of these hyperboloids, and the intersection may consist of one or two closed curves (now ignoring various limiting possibilities, which would need looking at in a full treatment). If it consists of a single curve, then this curve will be tangent to four generators of the hyperboloid, two of each system, and these will be common tangents to the three spheres. There is thus a 4<->1 correlation between the common tangents and values of Alpha in part of the range mentioned above. There will of course often be no common tangents to the three spheres, and I should single out just one special case in which one of the hyperboloids touches the third sphere along a circle - in this case every generator of this hyperboloid is a common tangent and vice versa, so that all 2*infinity common tangents correspond to one single value of Alpha. ============================================================================== From: rusin@math.niu.edu (Dave Rusin) Newsgroups: sci.math.num-analysis,sci.math.research,sci.math.symbolic Subject: Re: Family of lines tangent to 3 gives spheres Date: 23 Sep 1997 21:04:37 GMT Cassiano Durand wrote: >How can we describe parametrically the family of >lines simultaneously tangent to 3 given spheres (radii >and center coordinates are known)? Yesterday I responded with some simple information and a lot of gobbledygook from the computer; my back-of-the-mousepad analysis implied the family was a convoluted curve with no apparent parameterization. I'd like to give a more readable and thorough description of the situation now that I've had a chance really to think about it. As I showed in the previous post, the tangent lines are in 2-to-1 correspondence with the pairs (v,P) in R^3 x R^3 satisfying equations which may (upon scaling and translation) be written || v || = 1 || P || = 1 < P, v > = 0 < P, C > = < v, C >^2 + R < P, D > = < v, D >^2 + S where the constants C = -c/2 D = -d/2 R = -(1 + ||c||^2 - r^2)/4 S = -(1 + ||d||^2 - s^2)/4 are determined from the "initial geometry" -- the centers are assumed to be at points 0, c, and d, and the radii are 1, r, and s respectively. In the previous post, I tried to eliminate v to view the curve among the points P. This is foolish; clearly the equations will more easily allow the elimination of P leaving a nicer curve among the points v. As I do this, I will pay closer attention to the exceptional points of the elimination, and attempt a better geometric description of the problem. To avoid degeneracy, we shall assume the three spheres are distinct. It then follows that the centers must be different, if there are to be any tangent lines at all. In particular, we cannot have C=0, D=0, or D=C. It may be that the centers are collinear, that is, D = mC for some m (not equal to 0 or 1). In this case, the last two equations imply < v, C > = sqrt( (S-mR)/(m-m^2) ) < P, C > = (S-m^2R)/(m-m^2) (These right-hand sides are determined by the initial geometry.) This last equation forces P to be of the form xC + P' for some P' in C^\perp, where x is a specific number determined by the initial geometry; that is, P lies in a specific plane. Since we also know P lies in the unit sphere, it follows P lies in a specific circle, and in particular P' must be of a specific length (i.e., lie in a certain circle in C^\perp). Likewise v must have the form (+- y)C + v' for v' in some specific circle at the origin of C^\perp. Then the equation =0 forces to have some specific value, i.e., there is a calculable angle between P' and v'. So, as long as the three spheres' centers are collinear, we can calculate numbers x y z w and phi so that the tangent lines may be parameterized in the form P = x C + z cos(theta) e1 + z sin(theta) e2 v = y C + w cos(theta+phi) e1 + w sin(theta+phi) e2 as theta ranges over R (where I have fixed an orthonormal basis {e1, e2} of C^\perp.) The family of tangent lines is naturally isomorphic to a union of a few circles. (Of course this is not surprising: from collinearity we deduce a symmetry group of the configuration, which includes the circle group S^1.) So now in the sequel we may assume the centers are not collinear, and so the vectors C and D span a 2-dimensional space in R^3. In this case we distinguish two classes of tangent lines: those parallel to the plane containing C and D, and those others (which will be the generic case). The first tangent lines are the ones in which C, D, and v span only a 2-dimensional subspace of R^3. This can only occur if v = a C + b D for some a and b. We will show there is a finite number of such tangent lines. Indeed, 0 = = may be expanded using the last 2 equations to be a cubic in a and b; the equation |v|=1 expands to a quadratic in a and b. The two curves have finite intersection, i.e., there are at most 6 combinations of a and b allowing the equations to be satisfied. (More precisely, the two curves can only have infinite intersection if the "conic" is a union of two lines or if the cubic is the union of a line and the conic; the conditions under which these turn out to be true each reduce to a condition which implies C and D are collinear, which we have already excluded). We remark that the equations determining (a,b) will force (-a, -b) to be a solution if (a,b) is, as we know should be the case from the geometry. Thus there are at most 3 pairs {v, -v} for tangent lines of this type. Now assume that a and b are known (and thus that v is). The last two of our original five equations places P in the intersection of two non-parallel planes, i.e., on a line. Since P is also on the unit sphere, there can then be at most 2 such points of intersection, that is, at most 2 points P for each vector v. So we conclude that there are at most 6 lines which are parallel to the plane containing the centers of three non-collinear spheres and which are tangent to all three of those spheres. Now we look for lines tangent to the three non-collinear spheres which are _not_ parallel to the plane of the centers. In this case, C, D, and v are linearly independent. Note then that the last three equations of our original five are independent linear constraints determining P -- P lies in the intersection of three planes whose intersection is just a point. Then the equation |P|=1 constrains the set of possible v (as does the remaining equation |v|=1). So this part of the family of tangent lines is in a natural one-to-one correspondence with the curve of unit vectors v meeting this constraint. Hoping to analyze this curve, I returned to the conventions of the previous post (that the two other spheres were on the x-axis and the xy-plane, respectively) and had Dr. Maplev eliminate P from the four equations referring to it. (That is, use the last three to solve for P, and then substitute into |P|=1.) The resulting constraint has the form F1^2 = F2*v3^2, where F1 and F2 depend only on v1 and v2 (and R, S, C, and D). Thus v3 can also be easily eliminated, projecting our curve in R^3 down to a plane curve given by F1^2=F2*(1-v1^2-v2^2). It's not a pretty equation -- it's only a quartic in v2 but has 56 terms, of total degrees 0, 2, 4, and 6 in (v1,v2). Substituting in a few random values of R, S, C, and D suggests the curve is generically nonsingular and irreducible. Today I won't waste bytes displaying the equation: even though it's considerably simpler than yesterday's equation, it's not humanly comprehensible. The curve is rather complicated when graphed. Setting the parameters to e.g. C=(-6,0,0), D=(-10,-1,0), S=-1, and R=2, 1, 0, -1, -2 shows the situation when the spheres are nearly collinear and intersecting, as the middle sphere passes through the small one at the origin. A parameterization of the original family of tangent lines would project to a parameterization of this plane curve (or at least that portion of the plane curve lying in the image of the projection -- the portion in the unit disc). Conversely, if the plane curve could be parameterized, we extend to a parameterization of the curve in R^3 using v3 = sqrt(1-v1^2-v2^2) (clearly not a _rational_ parameterization, of course); the coordinates of P are then calculated as rational functions of these, giving a parameterization of the family of tangent lines. So the original request for a parameterization is, in the generic case, tantamount to a request for a parameterization of the plane curve. While I think this analysis is a little better than my first quick one, I'm still afraid there doesn't appear to be a parameterization which, for example, would avoid quite a bit of root finding for each setting of the parameter. (For example, one could set v2 = t*v1, and then for each choice of parameter t in (-oo, oo), solve a sextic polynomial to compute v1, and then obtain v2, v3, and P.) dave ============================================================================== To: rusin@math.niu.edu Subject: Re: Family of lines tangent to 3 gives spheres Date: Tue, 23 Sep 1997 16:54:04 -0500 From: crbd@cs.purdue.edu (Cassiano Durand) Dear Dave Rusin, Thank you very much for your reply. As you suggested I'll encode the parametrization as a set of elimination procedures, rather than try to find an explicit set of functions. Right now I am trying to reproduce the results you computed. I would appreciate if you could tell me how you eliminated v1 and v2 from the system > p1^2+p2^2+p3^2-1 > v1^2+v2^2+v3^2-1 > p3*v3+p1*v1+p2*v2 > R-2*a*p1 -a^2*v1^2 > S-2*b*p1-2*c*p2 -(b*v1+c*v2)^2 > where R=1+a^2-r^2, S=1+b^2+c^2-s^2. > Thank you Cassiano ============================================================================== Date: Tue, 23 Sep 1997 16:57:12 -0500 (CDT) From: Dave Rusin To: crbd@cs.purdue.edu Subject: Re: Family of lines tangent to 3 gives spheres Actually I just posted a refined version, which might make a little more sense; look for it when the moderators have a chance to pass it to the newsfeed. Meanwhile, perhaps you could tell me the context in which you wish to pursue this parameterization. Are you hoping to compute the lines numerically for a specific arrangement of spheres? Or are you looking for something more theoretical (e.g. connected components of the family of tangent lines)? Or...? I feel like I could probably be more helpful but I don't know which direction you're contemplating going. dave ============================================================================== To: Dave Rusin Subject: Re: Family of lines tangent to 3 gives spheres Date: Tue, 23 Sep 1997 17:34:30 -0500 From: crbd@cs.purdue.edu (Cassiano Durand) > Actually I just posted a refined version, which might make a little more > sense; look for it when the moderators have a chance to pass it to > the newsfeed. Good. > Meanwhile, perhaps you could tell me the context in which you wish to > pursue this parameterization. Are you hoping to compute the lines > numerically for a specific arrangement of spheres? Or are you looking for > something more theoretical (e.g. connected components of the family > of tangent lines)? Or...? I feel like I could probably be more > helpful but I don't know which direction you're contemplating going. > dave Sure. In fact, this problem came up as a part of a geometric constraint problem I want to solve. In the original problem, I have 3 points (p1, p2, p3) and 3 lines (l1, l2, l3). I know the coordinates of the points (for instance, you can assume that p1(0,0,0), p2(a,0,0) and p3(b,c,0)). You can also assume that a,b,c are not zero. The angles between each pair of lines are also known, as well as the distances from each line to each of the placed points. My goal is to find a systematic method to compute all possible solutions for such configuration, given the values of the angles between each line and the distance from each line to each point. Each line is at a certain distance from each of the points p1, p2 and p3. This is equivalent to say that each line is tangent to an sphere with center at p1, p2 and p3 with given radii. Suppose it's possible to find the parametrization of that family of lines tangent to the 3 spheres. Therefore I would have 3 1-parameter families of lines. Using the angle constraints, I'd have a system with 3 equations on these parameters. Each solution of this system is associated to a placement of the points and lines in accordance with the constraint values (distance and angle values). I've used homotopy comtinuation methods to find all the solutions of that "core" system (and therefore all the possible placements). The problem, however, is to find that "core" system. In the case of this problem, finding the parametrization explicitally, would imply in finding that core system. Let me know if you need/want more information. Again, Thank you very much Cassiano ============================================================================== Date: Wed, 24 Sep 1997 17:24:56 -0500 (CDT) From: Dave Rusin To: crbd@cs.purdue.edu Subject: Re: Family of lines tangent to 3 gives spheres Cool. I'm a little uneasy about one point: when you mention you have the angles between the lines, that suggests the lines are coplanar; do you mean that? If so, I would imagine there's not much chance the data you provide even _have_ a solution. I'll give this matter a little thought. Meanwhile, as promised, I'll provide more information about the elimination you wanted to see. I trust you've seen my second post by now. Here's an annotated Maple session (my comments preceded by '%' ). You'll see I do come pretty close to a parameterization: as in my last post, it comes down to parameterizing a plane curve. I decided to do so in polar coordinates: the points are (r cos(theta), r sin(theta) ) where, unfortunately, I don't have an easy formula for r as a function of theta, but I do get it down to r being a root of a cubic polynomial. If you're really desperate for an explicit formula, you could thus use the formula for roots of cubics to express r in terms of the parameter theta. Big yuk. I was in the process of working out examples to illustrate all this, but I wasn't sure what exactly I wanted to illustrate! You can get a family of pretty pictures showing some of the possibilities using a=-6, b=-10, c=-1, S=-1, and R near zero. dave %I call up Maple V on my system: |\^/| Maple V Release 3 (N I U) ._|\| |/|_. Copyright (c) 1981-1994 by Waterloo Maple Software and the \ MAPLE / University of Waterloo. All rights reserved. Maple and Maple V <____ ____> are registered trademarks of Waterloo Maple Software. | Type ? for help. %Enter the polynomials describing the family of tangents > e1:=v1^2+v2^2+v3^2-1: > e2:=p1^2+p2^2+p3^2-1: > e3:=p1*v1+p2*v2+p3*v3: > e4:=p1*a=(v1*a)^2+R: > e5:=(p1*b+p2*c)=(v1*b+v2*c)^2+S: %Maple can eliminate all the p's, that is, solve for P and find the %resulting constraint among the v's (other that the constraint e1=0) > readlib(eliminate): > eliminate({e2,e3,e4,e5},{p1,p2,p3}): > P:="[1]; 2 2 v1 a + R P := {p1 = ----------, a 2 2 2 2 2 2 b v1 a + b R - v1 b a - 2 v1 b v2 c a - v2 c a - S a p2 = - ----------------------------------------------------------, c a 3 2 2 2 2 2 2 p3 = (- v1 a c - v1 R c + v2 b v1 a + v2 b R - v2 v1 b a - 2 v1 b v2 c a 3 2 - v2 c a - v2 S a)/(v3 a c) } %And the condition v1 v2 v3 must satisfy is: > condition:=""[2][1]: %I'll write it compactly, in case you want to enter it yourself directly: > lprint(condition); v1^6*a^4*c^2+v1^4*a^4*c^2*v3^2+R^2*c^2*v3^2-a^2*c^2*v3^2+b^2*R^2*v3^2+S^2*a^2 *v3^2+v1^2*R^2*c^2+v2^2*b^2*R^2+v2^6*c^4*a^2+v2^2*S^2*a^2+b^2*v1^4*a^4*v3^2-2*b ^3*v1^4*a^3*v3^2+v1^4*b^4*a^2*v3^2+v2^4*c^4*a^2*v3^2+2*v1^2*a^2*R*c^2*v3^2+2*b^ 2*v1^2*a^2*R*v3^2-4*b^2*v1^3*a^3*v2*c*v3^2-2*b*v1^2*a^3*v2^2*c^2*v3^2-2*b*v1^2* a^3*S*v3^2-2*b^3*R*v1^2*a*v3^2-4*b^2*R*v1*v2*c*a*v3^2-2*b*R*v2^2*c^2*a*v3^2-2*b *R*S*a*v3^2+4*v1^3*b^3*a^2*v2*c*v3^2+6*v1^2*b^2*a^2*v2^2*c^2*v3^2+2*v1^2*b^2*a^ 2*S*v3^2+4*v1*b*v2^3*c^3*a^2*v3^2+4*v1*b*v2*c*a^2*S*v3^2+2*v2^2*c^2*a^2*S*v3^2+ 2*v1^4*a^2*c^2*R-2*v1^5*a^4*c*v2*b-4*v1^3*a^2*c*v2*b*R+2*v1^5*a^3*c*v2*b^2+4*v1 ^4*a^3*c^2*b*v2^2+2*v1^3*a^3*c^3*v2^3+2*v1^3*a^3*c*v2*S-2*v1*R^2*c*v2*b+2*v1^3* R*c*v2*b^2*a+4*v1^2*R*c^2*b*v2^2*a+2*v1*R*c^3*v2^3*a+2*v1*R*c*v2*S*a+v2^2*b^2* v1^4*a^4+2*v2^2*b^2*v1^2*a^2*R-2*v2^2*b^3*v1^4*a^3-4*v2^3*b^2*v1^3*a^3*c-2*v2^4 *b*v1^2*a^3*c^2-2*v2^2*b*v1^2*a^3*S-2*v2^2*b^3*R*v1^2*a-4*v2^3*b^2*R*v1*c*a-2* v2^4*b*R*c^2*a-2*v2^2*b*R*S*a+v2^2*v1^4*b^4*a^2+4*v2^3*v1^3*b^3*a^2*c+6*v2^4*v1 ^2*b^2*a^2*c^2+2*v2^2*v1^2*b^2*a^2*S+4*v1*b*v2^5*c^3*a^2+4*v1*b*v2^3*c*a^2*S+2* v2^4*c^2*a^2*S %Now eliminate v3 -- easy since condition is just F1 + F2*v3^2 > subs(v3^2=1-v1^2-v2^2,condition): > plane_crv:=simplify("): > nops(plane_crv); 56 %i.e., 56 summands; and here they are: > lprint(plane_crv); -b^2*v1^6*a^4+v1^4*a^4*c^2+b^2*v1^4*a^4-2*b^3*v1^4*a^3+v1^4*b^4*a^2+v2^4*c^4* a^2+R^2*c^2-a^2*c^2+b^2*R^2+S^2*a^2+2*v1^2*a^2*R*c^2+2*b^2*v1^2*a^2*R-4*b^2*v1^ 3*a^3*v2*c-2*b*v1^2*a^3*v2^2*c^2-2*b*v1^2*a^3*S-2*b^3*R*v1^2*a-4*b^2*R*v1*v2*c* a-2*b*R*v2^2*c^2*a-2*b*R*S*a+4*v1^3*b^3*a^2*v2*c+6*v1^2*b^2*a^2*v2^2*c^2+2*v1^2 *b^2*a^2*S+4*v1*b*v2^3*c^3*a^2+4*v1*b*v2*c*a^2*S+2*v2^2*c^2*a^2*S-2*v1^5*a^4*c* v2*b-4*v1^3*a^2*c*v2*b*R+6*v1^5*a^3*c*v2*b^2+6*v1^4*a^3*c^2*b*v2^2+2*v1^3*a^3*c ^3*v2^3+2*v1^3*a^3*c*v2*S-2*v1*R^2*c*v2*b+6*v1^3*R*c*v2*b^2*a+6*v1^2*R*c^2*b*v2 ^2*a+2*v1*R*c^3*v2^3*a+2*v1*R*c*v2*S*a-R^2*c^2*v2^2+a^2*c^2*v1^2+a^2*c^2*v2^2-b ^2*R^2*v1^2-S^2*a^2*v1^2+2*b^3*v1^6*a^3-v1^6*b^4*a^2-v1^4*a^4*c^2*v2^2-v2^4*c^4 *a^2*v1^2-2*v1^2*a^2*R*c^2*v2^2-2*b^2*v1^4*a^2*R+2*b*v1^4*a^3*S+2*b^3*R*v1^4*a+ 2*b*R*S*a*v1^2-4*v1^5*b^3*a^2*v2*c-6*v1^4*b^2*a^2*v2^2*c^2-2*v1^4*b^2*a^2*S-4* v1^3*b*v2^3*c^3*a^2-4*v1^3*b*v2*c*a^2*S-2*v2^2*c^2*a^2*S*v1^2 %Just to verify that v3 is gone: > indets(plane_crv); {a, S, b, c, R, v1, v2} %Next trick: parameterize the curve by angle theta, that is, view %v1=q*cos(theta), v2=q*sin(theta), then solve for q as a function of theta. > subs({v1=q*w1,v2=q*w2},plane_crv): %I happen to know this contains no odd powers of q so: > simplify(",{q^2=Q}): > newcrv:=factor("): %So now newcrv describes a cubic in Q whose roots tell us how far the %curve is from the origin in the direction (w1,w2). Let's just make sure %the v's and q's are gone and the degree is right: > indets(newcrv); {a, S, b, c, R, w1, w2, Q} > degree(newcrv,Q); 3 %OK, so here's your "parameterization". For each unit (direction) vector %(w1,w2), find the values of Q which make newcrv=0; there are either %1 or 3 such values. Whenever 0 <= Q <= 1 we can find the vector %v = (sqrt(Q)*w1,sqrt(Q)*w2, sqrt(1-Q)) and then find p1, p2, p3 by %substituting into P . So the parameterization is complete except for %the fact that we don't have a nice way to express Q as a function %of theta. %You can try to study the shape of the plane curve this way; you need to %study and see how, as theta changes, the set of roots Q changes in %the fundamental ways: passing thru Q=0, passing thru Q=1, or %passing from 1 root to 3 or back. I've got some formulas in this %direction for you if you want them but nothing definitive or particular %interesting. Let me know if you want to keep going along these lines. %I'm going home now; I may keep working on this. dave ============================================================================== Date: Thu, 25 Sep 1997 03:59:19 -0500 (CDT) From: Dave Rusin To: crbd@cs.purdue.edu Subject: Re: Family of lines tangent to 3 gives spheres > %I'm going home now; I may keep working on this. I did. First let me point out that I've thought about your larger problem with the 3 lines a little. Your search for a parameterization is, I think, a little misplaced for this application. On the one hand, you can't get it, since a parameterized curve is in particular connected, but this family is not, and as I understand what you want to do, it will be important not to miss branches of the curves. On the other hand, you don't need it, since your proposal to eliminate the parameter can be done algebraically, in principle, just as I have eliminated other variables. I'll return to that point a little later. I next want to express some concern whether you've proposed the right problem. As you pointed out, in the generic case you have 3 1-parameter families of lines, which you will restrict further by the condition that the lines form the appropriate angles; this adds three conditions of the simple form < v^(i), v^(j) > = cos(alpha_ij). Presumably for a generic configuration you then have a finite collection of possibilities. But there's still this point that I alluded to before: > I'm a little uneasy about one point: when you mention you have > the angles between the lines, that suggests the lines are coplanar... All you will know for your troubles is that, for each of these finitely many solutions, you have three lines, each of the appropriate distances from the three fixed points, whose direction vectors -- TRANSLATED TO THE ORIGIN -- have the right angles. There is nothing to guarantee that the lines actually cross. For example, if you rest an equilateral triangle on three equal spheres, that triangle is a solution to the problem posed by that arrangement of spheres; but so is the solution consisting of two of those lines plus a third one attached to the _underside_ of the spheres. Now let's see if we could do this algebraically (with or without intersections). For each line, follow the procedures I've been using. Since I now see that you don't want to assume any sphere has radius 1, you need to adapt the equations a little, but the gist is the same: we're looking for three pairs (v^(i), P^(i)) in R^3 x R^3, each satisfying 5 equations |v^(i)|=1, |P^(i)|=d_i, =0, =^2+R^(i), and =^2+S^(i) (the scalars and vectors d_i, c, d, R^(i), and S^(i) are fixed by the initial geometry). If you want the angles to be fixed, add three equations =cos(alpha_ij). This much should lead to a finite solution set for most settings of the initial geometry. If now you really want the lines to meet, you'll need to require that. The goal is to have a point which can be expressed both as P^(i)+tv^(i) for some t, and as P^(j)+uv^(j) for some u. Rearranging terms shows that this is equivalent to requiring P^(i)-P^(j) to be a linear combination of v^(i) and v^(j). The equation det([ P^(i)-P^(j) , v^(i) , v^(j) ]) = 0 is (for generic situations anyway) tantamount to the same thing. So it looks to me like you _can_ get the lines to meet, but only by adding 3 more equations. It's quite possible that some or all of these equations are implied by the others, but I'm dubious. Rather, it looks to me like these extra 3 equations will impose solvability relations on the parameters which describe the initial geometry! That is, not any combination of alpha_ij, d_i, c, d, R^(i), and S^(i) will allow a triangle to be suspended in space as you wish, but rather only those combinations in a codimension-3(?) subset. Loosely speaking, the situation is like this: put the three fixed points anywhere you want; decree arbitrarly all 9 distance betwen the fixed points and the lines; insist that the lines actually meet. Then you should be able to find a finite number of solutions, which means the angles at the corners are forced upon you. Let me also comment that, while I tried to analyze the whole situation as geometrically as possible in my second post, there's still quite a lot of algebra in the case of spheres and lines in general position. You can continue in this direction for the 3-line problem. But you're suggesting locating the possible lines with 21 equations in 18 variables and 15 parameters (18 if you don't use Euclidean symmetries). Since the 5-equation/6-variable/5-parameter case was already near the edge of my computer's facilities, I wouldn't even consider this approach in your larger situation. Possibly the algebraic-variety approach can be used in any specific example (that is, if the parameters are replaced by numbers) but even that's pushing it. The closest I've come to a geometric picture is this. As in my posts, you can pair off the tangent lines with points in a curve on the unit sphere. In your larger problem, you've now got 3 curves on the sphere, and you want to select a point on each subject to several additional criteria. Fixing the angles a_ij amounts simply to fixing the shape of the spherical triangle formed by the three points on the unit sphere (up to congruence); I imagine a fixed spherical triangle with one corner pinned into a curvy groove on the sphere, swung around until the second corner lands in a second curvy groove, and then the triangle slid around (with two corners riding in the grooves) until the third corner also lands in the third groove. Groovy! (But I don't have a geometric visualization for the condition forcing the lines really to meet.) Maybe I've misunderstood what kind of results you're hoping for in your larger problem -- are you generalizing some particular body of work? The question you posted to the newsgroup is just nice enough that we can make some geometrically appealing statements about the behaviour; but I can't see what humanly-comprehensible results you hope to find in your 3-line question. Let me know where you'd like to go from here. dave ============================================================================== Date: Thu, 25 Sep 1997 21:46:12 -0400 From: Cassiano Durand To: Dave Rusin Subject: Re: Family of lines tangent to 3 gives spheres Hi Dave, Dave Rusin wrote: > > Cool. I'm a little uneasy about one point: when you mention you have > the angles between the lines, that suggests the lines are coplanar; do you > mean that? I was not very explicit. I define the angle between 2 lines as the angle between their tangent vectors, therefore the lines can be skew. By saying that the angle between 2 lines l1 and l2 is \alpha, I am implying that =cos(\alpha). > If so, I would imagine there's not much chance the data you > provide even _have_ a solution. I'll give this matter a little thought. > If they were coplanar the whole thing would be inconsistent, but the thing makes sense, since they are not necessarilly planar. > Meanwhile, as promised, I'll provide more information about the > elimination you wanted to see. I trust you've seen my second post by now. > Yes. I've seen your second post. In fact "inspired" by your prior post I did myself the same derivation you posted, with the exception that I did not factor the factor F2. > > Here's an annotated Maple session (my comments preceded by '%' ). > You'll see I do come pretty close to a parameterization: as in my last > post, it comes down to parameterizing a plane curve. I decided to do > so in polar coordinates: the points are (r cos(theta), r sin(theta) ) > where, unfortunately, I don't have an easy formula for r as a function of > theta, but I do get it down to r being a root of a cubic polynomial. > If you're really desperate for an explicit formula, you could thus > use the formula for roots of cubics to express r in terms of the > parameter theta. > Big yuk. > Yes, Indeed...It's yucky! But much simpler than the parametrization I "attempted". Thank you very much for your interest. Sincerelly Cassiano ============================================================================== Date: Thu, 25 Sep 1997 23:22:53 -0400 From: Cassiano Durand To: Dave Rusin Subject: Re: Family of lines tangent to 3 gives spheres Dear Dave Rusin, I am writting this email to talk more about the 3-points-3-lines problem and to give you the "why" behind what I am doing (that's relative, of course :-)). Yes...The 3-lines-3-points problem is, in fact, quite big. As I mentioned in my previous email, the lines are not required to be coplanar. So far, my solution attempts are based on algebraic elimination of the system induced by the geometrical objects and constraints (with "some" geometrical reasoning). Each point is represented by their cartesian coordinates and the lines as a pair of vectors (p,t), s.t. ||t||=1 and =0. Therefore I have 21 equations and 27 variables. I fix 6 variables by placing some of the points and/or lines. In this particular attempt, 3 points (0,0,0), (a,0,0) and (b,c,0) were fixed. I've tried also placing a point with respect to a fixed line (e.g. the line is identified with the x-axis and the point is placed on the z-axis at the prescribed distance from the line) and placing a line with respect to other line (e.g. the line is identified as the x-axis and the second line - I can assume - is on a plane parallel to the xy-plane - the distance between the planes becomes a variable - and makes the prescribed angle with the first line). Placing 2 lines gives me more "algebraic freedom" for elimination. I've tried other representations, like representing the lines using Plucker coordinates in projective space and playing around with the Grassmanians and different algebraic expressions of the "distance-point-line" constraints. However, the "success" in any case is only partial. I've solved some similar problems involving points and planes. There I was able to create templates to solve (find _all_ possible coordinatizations for the geometric primitives involved) in seconds. However, this 3-points-3-lines problem is really stubborn, and the things look rather ugly (even though they were much uglier before). Let me talk a little bit about the "why" of all of this. I work on geometric modeling, more specifically in something called constraint solving. In a typical scenario, the user defines some geometric entities (simple like lines, points, or sets of them) and assigns some geometric constraints between them (distances, angles, incidence, ...). The engine (the constraint solver) should find a solution (a 3D placement) consistent with the assigned constraints. Usually there is more than 1 solution and the user has to be given the hability to choose between them. The user design is represented in combinatorial terms as a graph (constraint graph), which is then structurally partitioned into basic problems, like the 3-points-3-lines problem. The solutions for these basic problems are then combined to provide the solution for the whole. I am concerned with solving these basic problems. More specifically, in devising a framework to solve some of these problems systematically (You give the constraints, I give you the possible configurations). What I have used so far is a combination of algebraic and analytical tools (and some combinatorial ones). Right now the work is more theoretical, but who knows? > I can't see what humanly-comprehensible results you hope to find in > your 3-line question. :-)))))). I loved the quote. That's just one of the problems that can came up when a geometric design is broken up into smaller problems. > Let me know where you'd like to go from here. > I think I'll work a little more on the simplification. You gave me some more ideas for elimination that I'd like to experiment a little more. I'll let you know if something new comes up. I really appreciate your help. Thanks Cassiano