From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: geometric extremum problem Date: 24 Feb 1999 07:29:53 GMT Newsgroups: sci.math Keywords: closest point on circle cannot be classically constructed pascal ORTIZ wrote: >Suppose we are given two points A and B inside a circle C. > >How do you construct the point(s) M on the circle C >such MA+MB is as short as possible? > >By 'to construct' I mean 'to construct by means of ruler and compass'. A solution exists -- is that enough? By scaling we may assume C has radius 1; by translation we may assume it's at the origin; by rotation we may assume A and B have the same x-coordinate a, say. So I ran Maple through the calculations with C=the unit circle at the origin, A=(a, b), B=(a, c). By Lagrange multipliers the minimum of MA+MB will occur at a point M=(x,y) where (x^2+y^2=1 and) y d(MA+MB)/dx = x d(MA+MB)/dy, i.e. (y MA_x - x MA_y) = - (y MB_x - x MB_y ). Taking the derivatives introduces a square root so we square both sides and clear denominators: the resulting equation gives a multiple of x-a times a certain cubic in x and y. Using x^2+y^2=1 to eliminate y gives a quartic in x which is too ugly to reproduce. The point is just that the optimal x coordinate can be obtained by a succession of quadratic extensions over the field generated by 1, a, b, c, so that the point (x,y) is constructible from A, B, and C. (Tests with generic a,b,c show the quartic has group Sym(4) and in particular is irreducible.) dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: geometric extremum problem Date: 24 Feb 1999 07:49:23 GMT Newsgroups: sci.math pascal ORTIZ wrote: >Suppose we are given two points A and B inside a circle C. > >How do you construct the point(s) M on the circle C >such MA+MB is as short as possible? I had responded but now I see I had let my fingers get ahead of my brain. What I showed in fact was that _no_ construction is possible with a a compass and unmarked straightedge. Quoting myself: >By scaling we may assume C has radius 1; by translation we may assume >it's at the origin; by rotation we may assume A and B have the same >x-coordinate a, say. So I ran Maple through the calculations with >C=the unit circle at the origin, A=(a, b), B=(a, c). By Lagrange >multipliers the minimum of MA+MB will occur at a point M=(x,y) >where (x^2+y^2=1 and) y d(MA+MB)/dx = x d(MA+MB)/dy, i.e. >(y MA_x - x MA_y) = - (y MB_x - x MB_y ). Taking the derivatives >introduces a square root so we square both sides and clear denominators: >the resulting equation gives a multiple of x-a times a >certain cubic in x and y. Using x^2+y^2=1 to eliminate y gives >a quartic in x which is too ugly to reproduce. The point is just that >the optimal x coordinate can be obtained by a succession of ^^^...cannot! >quadratic extensions over the field generated by 1, a, b, c, so that >the point (x,y) is NOT constructible from A, B, and C. (Tests with >generic a,b,c show the quartic has group Sym(4) and in particular >is irreducible.) The group would have to be a 2-group in order for x to be a constructible number. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: geometric extremum problem Date: 7 Mar 1999 06:24:05 GMT Newsgroups: sci.math Steve Gray wrote: > This may be equivalent to a problem I have been wondering >about, namely: Given two points T and R, both outside a circle C, >construct that point P on the circle so that the lines TP and PR make >the same angle with the circle tangent at P. (Inspired by a computer >graphics application involving reflections from a cylinder.) > My problem, I have tentatively concluded, is not constuctable. I don't know whether the problems are "equivalent", but neither admits a ruler-and-compass solution. In your case, you are looking for the point (x,y) on a circle, say x^2+y^2=1, determined by two points outside the circle, say (a,b) and (c,d). The condition is that the rays must make the same angle with the tangent vector at P, which is the same as requiring that they make the same angle with the normal vector (x,y) at P. Well, the weaker condition that they make angles with the same square-of-cosine is expressed by requiring ( (PT) . normal )^2 / ||PT||^2 = ( (PR) . normal )^2 / ||PR||^2, i.e. 2 2 ((a - x) x + (b - y) y) ((c - x) x + (d - y) y) ------------------------ = ------------------------ 2 2 2 2 (a - x) + (b - y) (c - x) + (d - y) That and x^2+y^2=1 give you two equations in two unknowns. You can eliminate x, say, and deduce that y must satisfy an equation (d a - d - b + b c) (d a + d + b + b c) 2 2 2 2 + (-2 c d a + 2 d a + 2 b c - 2 a b c + 4 b d + 4 b d) y + ( 2 2 2 2 2 2 2 2 2 2 2 2 a + b - 4 a d + c + d - 4 b d + 2 b d - 4 c a - 4 c b + 2 c a) 2 2 2 2 2 3 2 2 2 2 4 y + (-4 b d - 4 d a - 4 b c - 4 b d) y + 4 (d + c ) (a + b ) y (This is a quartic since our conditions describe _four_ points on the circle: each of the angles can be either less than or greater than Pi/2. You just want the root making both inner products positive.) So the points you seek are easy enough to find numerically, but they're not in general going to be found with ruler-and-compass techniques: when, say, a=-1,b=2,c=1,d=3 we find the quartic to have Galois group S_4; since it's not a 2-group the points are not constructible in the classical sense. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: geometric extremum problem Date: 8 Mar 1999 21:39:09 GMT Newsgroups: sci.math Someone asked about taking two points A,B inside a circle and finding the point M on the circle which minimized the sum AM+BM. Then Steve Gray wrote: > This may be equivalent to a problem I have been wondering >about, namely: Given two points T and R, both outside a circle C, >construct that point P on the circle so that the lines TP and PR make >the same angle with the circle tangent at P. (Inspired by a computer >graphics application involving reflections from a cylinder.) > My problem, I have tentatively concluded, is not constuctable. I claimed, >I don't know whether the problems are "equivalent", but neither admits a >ruler-and-compass solution. So I should respond to this claim by Jiang Ching Kuen : >1.The line OA intersects the circle at C > and the line OB intersects the circle at D >2.BC intersects AD at E >3.OE intersects the circle at P >4.P is the point you want! I suppose O is the center of the circle. Since lines through O meet the circle twice, I'm going to assume we want the _ray_ OA to meet the circle at C, etc. I don't know which problem this procedure claims to solve, but in either case this is at best an approximation to the correct point. Let me first suppose this is to be a construction for the sum-of-the-lengths problem, so the new "P" is the old "M". Consider the case that A and B are of the form r*(cos(u),sin(u)) with u=u0 and -u0 respectively, for some r just less than 1, and u0 just less than Pi/2. By symmetry, your construction will lead to P = (1,0), giving a combined distance to the points of just under 2 sqrt(2). On the other hand, the choice P = (1,0) gives a combined distance of about 2, and is clearly enough less than 2 sqrt(2) that it will be a better choice than your construction gives, as we get close to extreme cases. Now let's suppose this construction is intended to solve the reflection problem. I'd guess that in the new post, "O" is the center of the circle, and "A" and "B" are the points previous called "T" and "R". I'll follow this new notation. If the circle is the unit circle at (0,0), A is essentially infinitely far up the vertical axis, and B = (sqrt(3),0), then your line AD is essentially vertical, meeting BC just left of the vertical line x=1. On the other hand, it's easy to see that in this case, the point P we want is the point where BC meets the unit circle. Moral: Don't be swayed by pictures. You've got to _prove_ that a proposed construction works. dave