Date: Jun 13, 1996 6:49 PM
Author: hawthorn@waikato.ac.nz
Subject: Re: simple proof?



In article <31BE4796.3A8B@cliff.backbone.uoknor.edu>, "Vincent R. Johns" <vjohns@cliff.backbone.uoknor.edu> writes:
> Ron Watkins wrote:
>>
>> Im wondering how one might prove (not necessarily formally) that the number
>> of times a circle would pass through a square is limited to the finite set
>> {0,2,4,6,8}.
>> Im not very skilled in proofs, nor am I looking for an extreemly formal
>> or technical proof. Perhaps somthing just a bit more rigirous than:
>> "it's obvious".
>>
>> While im at it, let me try and be a bit more formal myself.:
>>
>> Given a circle and a square (traditional definitions apply), the number of
>> intersections between these two objects is limited to the set given above
>> because why?
>> 1) If the circle is entirly inside or outside the square, the number of
>> intersections is 0.
>> 2) If the circle intersects the square once (along one more edges), the number
>> of intersections is 2 (once on each side (in and out)).
>> 3) The circle could intersect the square 4 times by having it clip 2 corners
>> off the square and 6 times by clipping 3 corners.
>> 4) If the circle clips all 4 corners, then the number of intersections is 8.
>>
>> Of course, one could argue that the circle could GRAZE the square and that it
>> would then only count once, but I still count that as 2 (with the same value).
>>

> ...
>
> Well, one observation that I might make is that the square consists of 4
> line segments, each of which intersects the circle in at most 2 points, so the
> total number of points cannot be greater than 8. This limits the set to
> {0, 1, 2, 3, 4, 5, 6, 7, 8}, and you may be able to eliminate some of the
> odd numbers by counting any points of tangency and any corners twice.
>
> -- Vincent Johns


You are observing one case of a general result. Let C and D be two
smooth simple closed curves in the plane, which are nowhere tangent to
each other. Such curves cross an even number of times.

Proof:
Jordan's curve lemma (which is intuitively obvious although harder
to prove rigorously) says that D (and C too for that matter) divides
the plane into two regions, an inside and an outside. Thus the points
on the curve C either lie inside D, outside D, or lie on D at a place
where C crosses from the inside to the outside or vice versa (since
the two curves are nowhere tangent).

Now start at a point x on C which does not lie on D. Suppose this point
lies outside D. As you travel around C, count the number of times
you cross the curve D. If you are point y, and you have crossed D an
even number of times, you are outside D. If you have crossed D an odd
number of times you are inside D. Of course, if you travel right around
the closed curve C back to x, you will be ending up at a point outside D,
and thus must have crossed it an even number of times. A similar analysis
holds of you start at an inside point.

QED

A square is not smooth, and you will need to patch the result up by
not allowing the circle to pass through a corner or something. But the
principle is the same.

Ian H