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