\section{\Sec0. Review of classical geometry}
\subsection{\Sbsec{\Sec2.7}. Oriented circles}
\note{Shouldn't the orientation of circles be given iby a normal vector? Worry about this in the 2SP.}
\note{find a uniform way to define orientation of lines, planes and circles.}
The test of whether a point is inside or outside a given circle plays a central role in many geometrical algorithms. In such algorithms, it is often convenient to treat straight lines (with the addition of the point at infinity) as circles with infinite radius. Topologically, the two concepts are equivalent: like a circle, a straight line divides the inversion plane ($\reals^2$ plus the point at infinity $\omega$) in two simply connected regions. However, there is no natural criterion for calling one of these regions the ``interior'' of the line, and the other the ``exterior''. We will resolve this ambiguity by specifying an orientation for the line, and substitute the notions of ``left side'' and ``right side'' for ``interior'' and ``exterior''. Mathematical cleanliness then requires we trat circles in the same manner. This justifies the following definitions:
\definition{\Def4}{An {\it oriented circle} is a circle on the extended plane endowed with a direction of traversal. The two regions of the extended plane bounded by $C$ are called the {\it left} and {\it right sides} of $C$, with respect to the direction of traversal of $C$.}
As we said before, an oriented straight line (with the point at infinity included) is a special case of oriented circle; its left and right sides are simply its left and right half-planes. For an oriented circle $C$ of finite radius, the left side is the interior or the exterior of the circle, depending on whether $C$ is oriented counter- or clockwise, respectively.
Like oriented lines and planes, an oriented circle $C$ can also be defined by a characteristic function, that is zero on $C$, positive on its left side, and negative on its right side.
\theorem{\Th{81}}{Every oriented circle $C$ has a characteristic function of the form
$$f(x,y)=Xx+Yy+Z(x^2+y^2)+W.\eqno(\Eq{78})$$}
\proof{If $C$ is a counterclockwise oriented circle with finite radius $r$ and center $c=(xc, yc)$, we can test whether $p=(x,y)$ lies inside or outside $C$ by comparing $\dist(c,p)=\sqrt{(xc-x)^2+(yc-y)^2}$ against $r$. Since neither quantity is negative, the same results will be obtained if we compare $(\dist(c,p))^2$ with $r^2$. So, the expression
$$\eqalignno{\nullr^2-[(xc-x)^2+(yc-y)^2](\Eq{79})\cr
\null\null=2xcx+2ycy-(x^2+y^2)+(r2-xc^2+yc^2)(\Eq{80})\cr}$$
is a characteristic function for $C$, and the theorem then holds with $X=2xc$, $Y=2yc$, $Z=-1$, and $W=r2-xc^2+yc^2$.
\pp If $C$ is {\it clockwise} oriented, the left side is the exterior, and the right side is the interior. The sign reversal of(\Eq{80}) will be then a characteristic function for $C$. The theorem is satisfied by taking $X=-2xc$, $Y=-2yc$, $Z=1$, and $W=-(r2-xc^2+yc^2)$.
\pp If the radius is infinite, the circle is an oriented straight line, which as we know has a characteristic function of the form $Xx+Yy+W$. This satisfies the theorem if we take $Z=0$.}
The ``converse'' of this theorem is also true: for any quadruple of coefficients $X, Y, Z$, and $W$ such that $X^2+Y^2-4ZW >0$, there is an oriented circle whose characteristic function is (\Eq{78}). If $Z=0$, the circle is simply the oriented line $\hol{X, Y\hom W}$. Otherwise it is a finite circle whose center $c$ and radius $r$ are given by
$$c=\left(-{X\over{2Z}}, -{Y\over {2Z}}\right)\eqno(\Eq{101})$$
and
$$r=\sqrt{xc^2+yc^2+W}={1\over{\leftv 2Z\rightv}}\sqrt{X^2+Y^2-4ZW}\eqno(\Eq{102})$$
The circle will be oriented counter- or clockwise depending on whether $Z$ is negative or positive.
\digress{The condition $X^2+Y^2-4WZ>0$ is equivalent to the requirement that $f(x,y)=Xx+Yy+Z(x^2+y^2)+W$ assumes both positive and negative values. If $X^2+Y^2-4ZW <0$, $f$ has everywhere the same (non-zero) sign as $Z$: the ``circle'' it represents has no boundary, and the whole plane lies on one side of it. When $X^2+Y^2-4ZW =0$, $f$ is zero at the point $c$ (\Eq{101}) and has the sign of $Z$ everywhere else.}
\note{Should this stuff go into chapter \Ch2? A sketchier version of it is already there.}
\note{Should we accept circles of radius zero?}
\note{Remark that (\Eq{79}) is faster to compute than (\Eq{80}) if we know the center and radius. Equation (\Eq{80}) is valuable because of the $\lambda$-mapping, and it also gives a more efficient formula for the case when $C$ is determined by three given points.}
\subsection{\Sbsec{\Sec2.8}. The quadratic mapping}
These results have a very nice geometrical interpretation. Consider the function $\lambda$ that lifts every point $(x, y)$ of the plane onto the point $(x, y, x^2+y^2)$ on the paraboloid of revolution $\Lambda$ defined by the equation $z=x^2+y^2$. This mapping has an amazing property: circles and straight lines on the $(x,y)$-plane are mapped to planar sction of $\Lambda$, end vice-versa!\figspace5cm
\note{Should we use $\lambda(x,y)=(x,y,-x2-y2)$? this would lead to $\incircle(a,b,c,d)=\POS(\lambda(a),\lambda(b),\lambda(c),\lambda(d))$, instead of $\NEG$.}
This fact follows directly from theorems \Th{81}: if the characteristic function of $C$ is $Xx+Yy+Z(x^2+x^2)+W$, then $(x,y)$ lies on $C$ if and only if its image $(x,y,x^2+y^2)$ lies on the plane $\pi(C)=\hol{X,Y, Z\hom W}$. Furthermore, the point $p$ is to the left of $C$ if and only if its image $\lambda(p)$ is to the left of $\pi(C)$. In particular, if $C$ is a counterclockwise oriented circle of finite radius, the plane $\pi(C)$ is oriented downwards ($Z$ is negative), so $p$ is to the left of $C$ if and only if its image is below $\pi(C)$.
Conversely, if a plane $\hol{X,Y,Z\hom W}$ cuts the paraboloid $\Lambda$, Any point $(x,y,z)$ on the intersection will satisfy both $z=x^2+y^2$ and $Xx+Yy+Zz+W=0$; the projection of that point will then satisfy $f(x,y)=Xx+Yy+Z(x^2+y^2)+W=0$. Moreover, by asssmption there will be points of $\Lambda$ on both sides of $\hol{X,Y,Z\hom W}$, so $f$ takes both positive and negative values. It follows that $X^2+Y^2-4ZW>0$, and therefore $f$ is a valid characteristic function for some circle.
\digress{These results can be generalized quite easily to other algebraic curves. For example, general conic sections (which include circles, ellipses, parabolas and hyperboles as special cases) have characteristic functions of the form $Xx+Yy+Ax^2+By^2+Cxy+W$. Therefore, the function $\xi:(x,y)\mapsto(x,y,x^2,y^2,xy)$ maps the problem of locating a point against a conic into that of locating a point of $\reals^5$ against a four-dimensional hyperplane of $\reals^5$. If the term $Cxy$ is omitted, the characteristic function describes an ellipse or hyperbole with main axes parallel to the coordinate axes.
\dp One can also extend this to higher dimensions: by the mapping $\lambda:(x,y,z)\mapsto(x,y,z,x^2+y^2+z^2)$, point location against a sphere is reduced to point location against a three-dimensional hyperplane of $\reals^4$.}
\footprob{\Prob{\Sbsec{\Sec2.8}.1}}{Study the problem of finding the minimum spanning ellipse in this light. What if we constrain the main axes of the ellipse to be parallel to the coordinate axes?}
\subsection{\Sbsec{\Sec2.9}. The oriented circle through three points}
The quadratic mapping makes the following result almost self-evident:
\theorem{\Th{41}}{Given any three distinct points $a, b, c$ on the plane, there is a unique circle that passes through them}
\proof{Consider the images $\lambda(a), \lambda(b), \lambda(c)$ of $a,b,c$. These three points are distinct and, since $\Lambda$ is a strictly convex surface, they are also non-colinear. There exists then a unique plane $\pi=\lambda(a)\lambda(b)\lambda(c)$ passing through those three points. The intersection of this plane with $\Lambda$ is a circle that passes through $a,b,c$. Any other circle also passing through $a,b,c$ would correspond to a plane passing through $\lambda(a),\lambda(b),\lambda(c)$ but distinct from $\pi$, a contradiction.}
The circle passing through $a,b,c$ can be oriented in two distinct ways. If we go once around the circle starting from $a$, we will encounter the three points either in the order $a,b,c$ or in the order $a,c,b$, depending on which way we go. This motivates the following definition:
\definition{\Def{29}}{The {\it (oriented) circle $abc$}, where $a,b,c$ are distinct points of the plane, is the classical (unoriented) circle passing through them, with the direction of traversal from $a$ through $b$ to $c$.}
If the three points determine a counterclockwise oriented triangle, then the circle $C=abc$ is oriented the same way. Under the quadratric mapping, $C$ maps to the intersection of $\Lambda$ with the plane $\pi=\lambda(a)\lambda(b)\lambda(c)$. The left side (that is, the interior) of $C$ maps to the part of $\Lambda$ that lies below $\pi$. According to the comments we made before, that is the {\it right} side of $\pi$.\figspace5cm
The oriented circle $acb$ passes through the same points as $C$, but has the opposite orientation. In general, if $a\pr, b\pr, c\pr$ is a permutation of the points $a,b,c$, the circle $a\pr b\pr c\pr$ will be oriented the same way as $C$ if the permutation is even, and the opposite way if it is odd. The orientation of the planes $\pi\pr=\lambda(a\pr)\lambda(b\pr)\lambda(c\pr)$ and $\pi$ are realted in precisely the same way. We conclude that the observation made in the preceding paragraph is true for {\it any} three points $a,b,c$, namely the left side of the circle $abc$ maps to the part of $\Lambda$ that is in the {\it right} side of the plane $\pi$.
Note that the proof of theorem \Th{41} still carries through if the three points $a,b,c$ are colinear; in that case, the plane $\pi$ is vertical, and the circle through $a,b,c$ degenerates to the line supporting them. The discussion above also carries through: the left side of the oriented line $abc$ maps to the part of $\lambda$ that lies to the right of $\pi$.
\proof{Let $p1, p2, p3$ be three sufficiently small pigs, and $\hbox{\bi W\/}$ an wolf, assumed to be simultaneously big and bad.}
\subsection{\Sbsec{\Sec2.10}. The $\incircle$ test}
We are now ready to define our geometric predicate, that applies to four points $a, b, c, d$ of the plane:
\definition{\Def5}{The predicates $\incircle(a, b, c, d)$ and $\outcircle(a,b,c,d)$ are true if the point $d$ lies respectively to the left and to the right of the oriented circle $abc$. Both predicates are false if two or more of $a,b,$ and $c$ coincide, or if $d$ is on the circle $abc$.}
In particular, when $a, b, c$ are counterclockwise oriented, $\incircle(a, b, c, d)$ is true if and only if $d$ lies inside the circle $abc$, and $\outcircle(a,b,c,d)$ is true if and only if $d$ is outside. When $a,b,c$ are clockwise oriented, these meanings are reversed: $\incircle$ is true {\it outside} the circle $abc$, and $\outcircle$ is true inside.\figspace4cm
\note{Edit this:} This predicate seems rather awkward to use in practice, since its meaning is dependent on the ordering of the points $a$, $b$ and $c$. Actually, this is not so: as for the algorithms we are going to see, in most uses of this predicate we know beforehand that $abc$ is a counterclockwise oriented triangle, so the intuitive interpretation suggested by its name is correct. However, definition \Def5 is better at handling degenerate cases situations (where $a$, $b$ and $c$ are collinear) than the simpler, intuitive interpretation.
According to what we discussed in the previous section, $\incircle(a,b,c,d)$ tests whether $\lambda(d)$ lies on the right side of the orietned plane $\lambda(a)\lambda(b)\lambda(c)$. Together with definition \Def{37B}, this proves the next lemma:
\lemma{\Th{40B}}{For any points $a,b,c,d$ on the plane,
$$\eqalign{
\incircle(a, b, c, d)
=\NEG(\lambda(a),\lambda(b), \lambda(c),\lambda(d))\cr
\outcircle(a, b, c, d)
=\POS(\lambda(a),\lambda(b), \lambda(c),\lambda(d))\cr}.\eqno(\Eq{103})$$}
From this equivalence we immediately derive a somewhat surprising fact: if the points $a,b,c,d$ are not on the same circle, then transposing any adjacent pair in the predicate $\incircle(a,b,c,d)$ will change the value of the predicate from true to false, or vice versa. In general, permuting the arguments of $\incircle(a,b,c,d)$ will either preserve or reverse its value, depending on whether the permutation has even or odd parity. The same of course is true of $\outcircle(a,b,c,d)$. In particular, we have
$$\incircle(a,b,c,d)\eqv\outcircle(b,c,d,a) \eqv\incircle(c,d,a,b)\eqv\outcircle(d,a,b,c).$$
We can see that in $\incircle(a,b,c,d)$ all four points play a symmetric role, even though from the definition $d$ seems to be special.
From theorem \Th{40B} we also conclude that
\theorem{\Th{43}}{The predicate $\incircle(a, b, c, d)$ is true if and only if
$$\Delta(\lambda(a), \lambda(b), \lambda(c), \lambda(d))=
\detmat{\matrix4{
xayaxa^2+ya^21\cr\vsk3
xbybxb^2+yb^21\cr\vsk3
xcycxc^2+yc^21\cr\vsk3
xdydxd^2+yd^21\cr}}\eqno(\Eq7)$$
is negative. The predicate $\outcircle(a, b, c, d)$ is true if and only if this determinant is positive.}
This theorem gives a reasonably efficient formula for computing the $\incircle$ predicate.
\footprob{\Prob{\Sbsec{\Sec2.10}.1}}{Find the most efficient way to compute the $\incircle$ test. {\it Hint\/}: Nine subtractions reduce the determinant of equation \Eq6 to a $3\times 3$ determinant. Note that we need only the sign of $\Delta$, not its absolute value. {\it Another hint\/}: Consider expanding (\Eq6) by the third column; who knows, it may be better.}
\footprob{\Prob{\Sbsec{\Sec2.10}.2}}{Study the numerical stability of the determinant (\Eq7), and develop ``numerically robust'' algorithms for computing it.}
\subsection{\Sbsec{\Sec2.11}. Properties of the $\incircle$ test}
The $\incircle$ property has an alternate geometrical interpretation that is in some situations easier to use:
\lemma{\Th{20C}}{Let $a,b,c,d$ be in counterclockwise order the four distinct vertices of a simple quadrilateral $Q$ (not necessarily convex). Let $\hat a, \hat b, \hat c, \hat d$ be the corresponding internal angles of $Q$. Then the following conditions are equivalent:
\tp 1. $\incircle(a,b,c,d)$;
\tp 2. $\hat a+\hat c < 180\deg$;
\tp 3. $\hat b+\hat d > 180\deg$;
\tp 4. $\hat a+\hat c < \hat b+\hat d$.}
\proof{Conditions 2, 3 and 4 are obviously equivalent, since the interior angles of any simple quadrilateral add to exactly $360\deg$. Let us show that 1 and 2 are equivalent.\figspace3cm
\pp Because of our assumptions on $Q$, the circle $C=\circle(a,b,c)$ is counterclockwise oriented. The arcs $cda$ and $abc$, respectively subtended on $C$ by the angles $\hat b$ and $\hat d$, add up to $360\deg$. As we know from elementary geometry, the measure of $\hat b$ is half of the arc $cda$. Also, the angle $\hat d$ will be more than half of the arc $abc$ if and only if $d$ is inside the circle $C$\foot\dag{Note that this holds even if $Q$ is concave at $d$, that is, if $a$ and $d$ lie on the same side of the line $bd$.}. We conclude that $\hat a+\hat c <{1\over2}360\deg=180\deg$ if and only if $d$ is to the left of $\circle(a,b,c)$, that is, if and only if $\incircle(a,b,c,d)$.}
\digress{Another way of testing whether four points are cocircular is given by Ptolemy's theorem, which states that $a,b,c,d$ lie on the same sircle (in that order) if and only if
$$\bar{ab}\times\bar{cd}+\bar{bc}\times\bar{ad} = \bar{bd}\times\bar {ac}$$
This theorem however cannot be used to decide whether $d$ is inside or outside the circle $abc$, as we always have
$$\bar{ab}\times\bar{cd}+\bar{bc}\times\bar{ad}\geq \bar{bd}\times\bar {ac},$$
with equality only when the four points are cocircular. In fact, the quantity one obtains by rendering $\bar{ab}\times\bar{cd}+\bar{bc}\times\bar{ad} -\bar{bd}\times\bar {ac}$ radical-free is exactly the square of the determinant $\Delta(\lambda(a),\lambda(b),\lambda(c),\lambda(d))$ above. \note{Check this again. Is the square really thre from the beginning, or is it introduced in the elimination of radicals?}}
\note{Historical note: augment.} The quadratic mapping as a means of transforming circles in the plane into planes in three-space is a rather old idea. The basic principles of the $\incircle$ test appear in a classic paper by Jung (do they???). However, it is not as well known as it should, and in fact it has been independently rediscovered many times.