Circle Problem

Given three points in the plane, not forming a line, find an equation for the circle passing through them. Let the points be (x1,y1), (x2,y2), (x3,y3). Then we get 3 equations:

(xi - h)^2 + (yI - k)^2 = r^2 for i = 1, 2, 3.

There are 3 unknowns, h, k , and r. But the equations are nonlinear. What to do? We expand the equations:

xi^2 + 2hxi + h^2 + yi^2 - 2kyi + k^2 = r^2 for i = 1 ,2, 3.

Then rewrite as

-2xi * h -2yi * k + 1 * h^2 + 1 * k^2 - 1 * r^2 = - (xi^2 + yI^2) for i =1,2,3.

Now think of h, k, h^2, k^2 and r^2 as being 5 unknowns. We put the 3 equations with 5 unknowns into matrix form: (Spacing problems may occur because of font differences. Edit as needed.)

[ h ]

[ -2x1 -2y1 1 1 -1 ] [ k ] [ -(x1^2 + y1^2) ]

[ -2x2 -2y2 1 1 -1 ] [ h^2] = [ -(x2^2 + y2^2) ]

[ -2x3 -2y3 1 1 -1 ] [ k^2] [ -(x3^2 + y3^2) ]

[ r^2 ]

The idea is we will solve this system. Although a 3x5 systems do not have unique solutions, it will turn out that we always we be able to read off h and k. (See homework problems below). Then we use the first data point to get r.

Example: Use (0,0), (1,1), (2,1).

> A:=matrix([[0,0,1,1,-1],[-2,-2,1,1,-1],[-4,-2,1,1,-1]]);

> b:=matrix([[0],[-2],[-5]]);

> linalg[rank](A);

rank 3 means that the points do not form a line. Why is that???

> linalg[linsolve](A,b);

We get h=3/2 and k=-1/2. Then

> r:=sqrt((0-3/2)^2 + (0+1/2)^2); evalf(r);

Circle Program

This is a maple program for plotting a circle given three points in the plane. It uses the linalg, plots and plottools packages, though these need not be loaded.

> draw:=proc(x1,y1,x2,y2,x3,y3)
local A,b,sol,r,h,k:
A:=matrix([
[-2*x1,-2*y1,1,1,-1],
[-2*x2,-2*y2,1,1,-1],
[-2*x3,-2*y3,1,1,-1] ]);
b:=matrix([
[-(x1^2+y1^2)],
[-(x2^2+y2^2)],
[-(x3^2+y3^2)] ]);
if linalg[rank](A)<3 then
ERROR(`Points are colinear. Rank is`, linalg[rank](A))
fi;
sol:=linalg[linsolve](A,b);
h:=sol[1,1];k:=sol[2,1];r:=((x1-h)^2+(y1-k)^2)^.5;
lprint(`Center is (`,evalf(h),`,`,evalf(k),`). Radius is`,r,`.`);
plots[display](
plottools[circle]([h,k],r,color=red,thickness=2),
plot([[x1,y1],[x2,y2],[x3,y3]],style=point,symbol=circle,color=blue),
plot([[h,k]],style=point,symbol=circle,color=black),
plot([[h,k],[x1,y1]],style=line,color=green,thickness=2),
plot([[h,k],[x2,y2]],style=line,color=green,thickness=2),
plot([[h,k],[x3,y3]],style=line,color=green,thickness=2) );
end:

> draw(0,0,1,1,1,2);

Center is ( -.5000000000 , 1.500000000 ). Radius is 1.581138830 .

>

Try various points and see what draw does.

Homework

1 [Computer Theory]: Prove that the circle program above will always work (or find a counterexample!). Write up your proof as part of a letter to a company that wants to pay you big bucks for it, but they aren't sure it works as advertized. You need to prove two things: That rank=3 means the points are not colinear; and that the pivots in rref(A) will always be placed so that h and k have unique solutions.

2 [Least Squares]: You are given a set of N data points in the plane. Find the "best" circle.

3 [Sphere]: Prove that 4 non-coplanar points in R^3 determine a sphere.