\input CS445Hdr
% This is CS445N3.tex of January 19, 1982  1:32 AM
\def\title{Lectures 3--4}
\def\header{3. Convexity}

\chap{\header.}
\sect{3.1. Convex sets.}

\def\msc{\mathop{\hbox{\rm msc}}}
\def\mss{\mathop{\hbox{\rm mss}}}

A subset $F$ of a $k$-dimensional Euclidean space $\Sscr$ is said to be {\it convex} if for any two points $a,b\in F$ the straight line segment $ab$ joining them is completely contained in $F$.\par

Examples of convex sets in the plane are single points, straight lines, circles, half-planes, triangles, and so forth. As is well known, a polygon with four or more sides need not be convex, but rectangles and regular polygons are. In spaces with dimension $k$ higher than 2, examples of convex sets are linear subspaces, spheres, $k$-simplexes, and $k$-cubes.\par

A {\it convex combination} of $n\geq1$ points of $\Sscr$ is defined by the following recursive rules: the point $p$ is the (only) convex combination of $\leftset p \rightset$, and the convex combinations of $\leftset p
1, p
2, \ldotss, p
n \rightset$ are all the points in the straight line segments connecting $p
n$ to convex combinations of $\leftset p
1, p
2, \ldotss, p
{n-1}\rightset$.\par

In particular, the convex combinations of two points $p, q$ are the points of segment $pq$, and those of three non-collinear points $p,q,r$ constitute the triangle $pqr$. It follows immediately from the definition that a convex combination of points taken from a convex set $F$ is itself a point of $F$\par

Any point $t$ in the straight line segment $pq$ can be written as $\lambda p +(1-\lambda)q$, where  $\lambda $ is a real number such that $0\leq \lambda\leq 1$. As a consequence of this fact, any convex combination of $\leftset p
1, p
2, \ldotss, p
n \rightset$ can be written as $\lambda
1p
1+\lambda
2p
2+\cdots+\lambda
np
n$ with $0\leq \lambda
i\leq 1$ and $\sum
i\lambda
i=1$. \par

\sect{3.2. Helly's theorem.}

The definition of convexity is very simple, and yet it has lots of amazing consequences. It is easy to check, for example, that the intersection of a family (finite or infinite) of convex sets is a convex set; in fact, a convex polygon with $n$ sides is the intersection of $n$ half-planes, each defined by the supporting line of a side of the polygon.\par

The convexity of a set is preserved by operations such as translation, rotation, scaling, projection, and in general by all operations that map line segments into line segments.  Another useful property is given by the theorems below:

\lemma{3.1}{If four convex subsets $F
1, F
2, F
3$ and $F
4$ of the plane are such that each three of them have a common point,  then all four have a common point.}
\proof{For $i=1,2,3$ and $4$, let $p
i$ be a point in $\inter
{j\not=i}F
j$ (i.e. in the three figures other than $F
i$). Any two of these points (say $p
1$ and $p
2$) will both be contained in the sets with complementary indices ($F
3$ and $F
4$), and so the segment $p
1p
2$ will belong to $F
3\int F
4$. Any three points (say, $p
1, p
2$ and $p
3$) will be contained in the set with complementary index ($F
4$), and so will the triangle $p
1p
2p
3$.\par

\hp If the four points determine a convex quadrilateral, its diagonals (say, $p
1p
2$ and $p
3p
4$) will have a common point $q$ that belongs to all four sets. If the quadrilateral is not convex, one of the points (say $p1$) will be inside the triangle determined by the other three; all points on this triangle belong to $F
1$ by the argument above, and $p
1$ belongs to $F
1\int F
2\int F
3$ --- hence it belongs to all four sets.}

\theorem{3.2 {\rm (E. Helly, 1923)}}{If $F
1, F
2, \ldotss, F
n$ are convex subsets of the plane such that any three of them have a point in common, then they all have a point in common.}
\proof{If $n\leq 3$, the result is trivial; if $n=4$ it reduces to the preceding lemma. Let's assume then that $n>4$.\par

\hp For any $i,j\in [1..n-2]$, lemma 3.1 above tells us that $F
i, F
j, F
{n-1}$ and $F
n$ have a common point; therefore, if we define $F
{n-1}\pr$ to be $F
{n-1}\int F
n$, we can say that any three of the sets $F
1, F
2, \ldotss, F
{n-2}, F
{n-1}\pr$ have a common point, and the result follows by induction on $n$.}

The convexity of the sets $F
i$ and the finiteness of $n$ are essential; if either restriction is lifted, the theorem becomes false, as is shown by the couterexamples below.\fig4 The theorem is still true for a collection of infinitely many {\it bounded} sets, but the proof is outside the scope of the course.\par

Helly's theorem generalizes nicely to $k$-dimensional spaces as stated below. The one-dimensional version is known as {\it Cantor's theorem}.\par

\theorem{3.3}{Given $n$ convex sets in a $k$-dimensional space, if any $k+1$ of them have a common point, then they all have a common point.}

Helly's theorem may seem somewhat useless and artificial, but actually it is a very powerful result. For example, consider the theorem below:\par

\theorem{3.4}{Given $n$ points in the plane, if any three of them can be covered by a circle of radius $r$, then they all can be covered simultaneously by such a circle}
\proof{Two (or more) points can be covered by a circle of radius $r$ iff the circles of radius $r$ centered on them have a common point (which can be taken to be the center of the covering circle). Therefore, what we want to prove is equivalent to the  statement ``given $n$ circles of radius $r$ on the plane, if any three have a common point, then all have a common point'', which is true by Helly's theorem.}

This result can be used to show that the minimum spanning circle of $n$ points in the plane is determined by at most three of them.  Note that this proof can be generalized to dimensions higher than two without using any sophisticated geometrical constructions in $k$-space. An analogous result for the $\msc$ of a collection of figures (rather than points) follows from the infinite version of Helly's theorem.\par

\digress{A curious topic related to the minimum spanning circle problem is the following question: what is the figure of smallest area that can cover any figure of diameter 1? A circle with diameter 1 will not do: for example, it fails to cover an equilateral triangle of side 1. From Jung's theorem we know that a circle of radius ${\sqrt3}/3$ will do the trick, but this figure is not the minimum-area one. A regular hexagon inscribed in such a circle works equally well, and even smaller figures have been found that satisfy the stated condition. The problem is still an open one.}

\sect{3.3. Interior, exterior and boundary.}

A {\it ball} in a $k$-dimensional space $\Sscr$ is a nonempty $k$-dimensional open sphere, i.e. the set $\leftset x \in\Sscr\relv \seg{xp} < \epsilon\rightset$, for some point $p\in\Sscr$ and some positive radius $\epsilon$.\par

Any subset $F\subset \Sscr$ classifies the points of $\Sscr$ in three disjoint categories: we say that a point $p$ is on the {\it interior} of $F$ if there exists a ball centered at $p$ and entirely contained in $F$; $p$ is on the {\it exterior} of $F$ if thre is a ball with center $p$ completely outside $F$; and $p$ is on the {\it boundary} of $F$ if it satisfies neither of these conditions\foot1{Note that the space $\Sscr$ must be specified in order to make these definitions precise. For example, the boundary of a line segment $F$ has only two points if $\Sscr$ is taken to be its supporting line, and is the whole $F$ if $\Sscr$ is taken to be a containing plane.}.\par

The interior is always a subset of $F$, and the exterior is always disjoint from $F$. In the general case, each (or both) can be empty, and the boundary may be contained in $F$ ($F$ is then said to be {\it closed}), may be in its complement ($F$ is {\it open}), or may intersect both. Points in the interior or in the exterior of $F$ are also said to be {\it (strictly) inside} or {\it outside} $F$, respectively.\par

The following results refer to a {\it convex} set $F$ and a point $a$ inside it (i.e, in its interior):\par

\lemma{3.5}{If $b$ is any point of $F$, then any point $c\neq b$ on the segment $ab$ is in the interior of $F$.}
\proof{If $b=a$ the result is trivial, so assume $b\neq a$. By definition of interior, there is a ball $S
a\subset F$ with center $a$ and radius $\epsilon>0$. For every point $a\pr\in S
a$, consider the point $c\pr$ on the segment $a\pr b$ such that $\seg{c\pr b}/\seg{a\pr b} = \seg{cb}/\seg{ab}$. It is easy to check that the set of such $c\pr$s is a ball $S
c$ centered at $c$.\fig3
By convexity of $F$, we conclude $S
c\subset F$ and therefore $c$ is interior}.

\lemma{3.6}{If $b$ is any point on the boundary of $F$, then any point $c\neq b$ on the segment $ab$ is in the interior of $F$.}
\proof{By definition, there is some ball $S
a$ of radius $\epsilon>0$ centered at $a$ that is entirely in $F$. Let $d$ be a point on segment $cb$ distinct from $c$ and $b$. For each point $a\pr$ in $S
a$, consider the point $b\pr$ such that $d$ is on the segment $a\pr b\pr$ and $\dist(b\pr,d)/\dist(a\pr,d)=dist(b,d)/\dist(a,d)$; the set of such points $b\pr$ will be a ball $S
b$ centered at $b$.\fig3
By definition of boundary, some point $b\pr$ of $S
b$ must be in $F$; the segment from $b\pr$ to its corresponding point $a\pr$ passes through $d$. Therefore, $d$ is in $F$; by lemma 3.5, we conclude that $c$ is inside $F$.}

\lemma{3.7}{If $b$ is a point outside $F$, then the segment $ab$ meets the boundary of $F$ at exactly one point.}
\proof{Since $a$ is in $F$ and $b$ is not, there must be a point $c$ on segment $ab$ that is the point farthest away from $a$ with the property that all points between $a$ and $c$ are in $F$; we claim that $c$ is on the boundary of $F$.\fig3
By the choice of $c$, any point $a\pr\neq c$ on segment $ac$ will be in $F$, and for any $\epsilon>0$ there exists a point $b\pr\notin F$ on segment $cb$ with $\dist(c,b\pr)<\epsilon$. So, any ball centered at $c$ will contain a point in $F$ and a point of its complement.\par

\hp Now suppose there were two distinct boundary points $c,c\pr$ on segement $ab$; we can assume that $c$ is between $a$ and $c\pr$. Then, by lemma 3.6, the point $c$ would be interior, a contradiction.}

The following theorem lists some of the possible ways in which a segment may be placed relative to a convex set:

\theorem{3.8}{Let $ab$ be a line segment and $F$ be a convex set. Then:\par
\tp a) if $a$ and $b$ are interior to $F$, then the whole segment $ab$ is interior to $F$;\par
\tp b) if $a$ is interior and $b$ is on the boundary, then the rest of $ab$ is in the interior;\par
\tp c) if $a$ is interior and $b$ is exterior, then the segment $ab$ contains exactly one boundary point;\par
\tp d) if $a$ and $b$ are on the boundary, then the rest of $ab$ is either all on the interior or all on the boundary of $F$.}
\proof{The proof for each case follows easily from lemmata 3.5, 3.6 and 3.7 above, and is left to the reader.}

The following is an important consequence of these results:

\theorem{3.9}{If a straight line $\lscr$ passes through an interior point $a$ of a bounded convex set $F$, then $\lscr$ meets the boundary of $F$ at exactly two points.}
\proof{If $F$ is bounded by a ball of radius $r$, the two points $b,b\pr$ on $\lscr$ at distance $2r+\epsilon$ from $a$ must be exterior to $F$. Lemma 3.7 applied to the pairs $ab$ and $ab\pr$ gives us two distinct points of $\lscr$ belonging to the boundary of $F$. There are no further points, since the rest of $\lscr$ does not intersects $F$.}

The converse of this result is also true, namely\par

\theorem{3.10}{If a bounded set with nonempty interior $F$ is such that any line $\lscr$ through the interior of $F$ meets at most two points of its boundary, then $F$ is convex.}
\proof{First note that from the hypothesis we can derive the following fact: the intersection of $F$ and any line passing through an interior point of $F$ consists of a single line segment; the two endpoints of this segment are boundary points of $F$, and the others are interior to $F$.\par

\hp If $F$ were not convex, there would be two points $a,b\in F$ and a point $c$ in the segment $ab$ such that $c\notin F$. By the above fact we can say that $a$ and $b$ cannot be interior points, so they must be on the boundary of $F$.\fig4

\hp Let $p$ be a point in the interior of $F$, and $\lscr$ be the line through $a$ and $p$. Since there is a whole ball of interior points around $p$, we can choose $p$ so that $\lscr$ is not collinear with $ab$. By what we said before,  $\lscr\int F$ is a single line segment, and both $a$ and $p$ are in it. It follows that the segment $ap$ (except perhaps for $a$) is interior to $F$.\par

\hp The point $c$ must be an exterior point, and therefore there is a ball $S\notin F$ of radius $\epsilon$ centered at $c$. Let $a\pr$ be a point of $ap$ such that $\seg{a\pr a}<\epsilon$; then the line $t$ through $a\pr$ and $b$ will cross the sphere $S$. But then $t$, which passes through interior points of $F$, will contain two points $a\pr,b\in F$ separated by a point not in $F$ --- thus contradicting our first conclusion. It follows that such $c$ cannot exist, and therefore $F$ is convex.}

\digress{It has been conjectured in class that the boundedness condition on $F$ can be dropped if we replace ``at most two'' by ``exactly two'' in the statement of the theorem. If you can find a proof or a counterexample for this conjecture, we would be glad to hear about it.}

\sect{3.4. Figures.}

We define a {\it figure} as being a subset $F$ of $\Sscr$ that is closed (i.e., contains it own boundary) and has nonempty interior. By restricting our attention to figures, instead of general point sets, we will be able to exclude most pathological cases while retaining the ``interesting'' ones, and this will make for simpler theorems and shorter proofs.\par

We can show that by requiring figures to have nonempty interior we are not throwing away any terribly intersting cases:\par

\theorem{3.11}{If a convex set $F$ in the plane has no interior, then it is contained in a straight line}
\proof{Suppose $F$ is not contained in any straight line. Then we can find three points $p,q,r\in F$ that determine a non-degenerate triangle, which is entirely contained in $F$. A point in the interior of the triangle would also be in the interior of $F$.}

The converse is also true; and, in general, a convex set in $k$-space has interior points iff it is not contained in any $(k-1)$ dimensional subspace. The only convex sets in a straight line are\par

\def\hi{\penalty-1\hangindent 15pt after0}
\vskip0pt plus6pt
\hi\bu  the empty set,\par
\hi\bu  a single point,\par
\hi\bu  a line segment, (with or without its endpoints),\par
\hi\bu  a ray (with or without its origin),\par
\hi\bu  the whole line.\par\vskip0pt plus6pt

and the reader will surely agree that they would make rather boring figures.\par
In the next sections we will assume all figures to be bounded and two-dimensional, unless stated otherwise.

\sect{3.5. Supporting lines.}

A {\it supporting line} of a figure $F$ is a line $\lscr$ passing through some of its points and such that $F$ is entirely contained in one of the half-planes determined by $\lscr$.\fig3\par

It is easy to see that the points where $\lscr$ meets $F$ are boundary points of $F$. If $F$ is a convex figure, the converse also holds:\par

\lemma{3.12}{A line $\lscr$ that contains a point of a convex figure $F$ but no interior point must be a supporting line.}
\proof{Suppose $F$ has points on both sides of $\lscr$; let $a$ be an interior point, $b$ any point of $F$ on the opposite side of $\lscr$, and $c$ the point where segment $ab$ crosses $\lscr$.\fig3 By lemma 3.5 $c$ is interior, contradicting the hypothesis.}\par

A {\it supporting half-plane} of $F$ is a (closed) half-plane that contains $F$ and is bounded by a supporting line of $F$.  It is convenient to define the orientation of a supporting line in such a way that the figure is in the half-plane at its ``left''.  The {\it normal} or {\it perpendicular direction} to a supporting line is a unit vector $d$ perpendicular to the supporting line and pointing away from the figure, i.e. towards the ``right''.\par

It is also convenient to orient counterclockwise the boundary of convex figures.  If the boundary is scanned in this direction, the orientation of each supporting line will be found to agree with the direction of the scan at the points of contact.\fig3\par

\lemma{3.13}{Given a unit vector $d$,  a figure $F$ has exactly one supporting line whose normal is $d$.}
\proof{Consider the projection of the figure onto a line parallel to $d$; the projection will be bounded, nontrivial and closed, and therefore will have a furthest point $p$ in the direction $d$.\fig4 The line $\lscr$ perpendicular to $d$ and passing through $p$ will meet $F$, and $F$ will be entirely contained in the half-plane delimited by $\lscr$ and opposite to $d$. This proves it to be a supporting line of $F$.}

A supporting line $\lscr$ may meet a figure $F$ in more than one point. If the figure is convex, the set $\lscr\int F$ must be convex, and therefore must be a line segment.  If we disregard orientations, for each direction $d$ there are two distinct supporting lines $\lscr
1$ and $\lscr
2$ (one on each side of $F$) perpendicular to $d$ and therefore parallel to each other. The segments $\lscr
1\int F$ and $\lscr
2\int F$ need not be ``facing across each other'', i.e. there may not be any line parallel to $d$ that intercepts them both. This makes the next result a little bit surprising:

\lemma{3.14}{Let $\lscr
1$ and $\lscr
2$ be a pair of parallel supporting lines for the convex figure $F$ such that $\dist(\lscr
1,\lscr
2)$ is  maximum. Then $\lscr
1$ and $\lscr
2$ meet $F$ each at a single point, and the segment connecting those two points is perpendicular to $\lscr
1$ and $\lscr
2$.}
\proof{Let $a
1$ and $a
2$ be points in $\lscr
1\int F$ and $\lscr
2\int F$, respectively. Consider then the pair of supporting lines $t
1$ and $t
2$ perpendicular to $a
1a
2$.\fig4
By hypothesis, $\dist(t
1,t
2)\leq\dist(\lscr
1,\lscr
2)\leq\seg{a
1a
2}$; on the other hand, the points $a
1$ and $a
2$ must be contained in the strip between $t
1$ and $t
2$, so $\dist(t
1,t
2)\geq\seg{a
1a
2}$, and we conclude $\dist(\lscr
1,\lscr
2)=\seg{a
1a
2}$. This can only happen if $a
1a
2$ is perpendicular to $\lscr
1$ and $\lscr
2$.\par

\hp There can't be a distinct point $a
1\pr\neq a
1$ in $\lscr
1\int F$, since the same argument can be used to show that $a
1\pr a
2$ is also perpendicular to $\lscr
1$ --- an impossibility. The same holds for $\lscr
2\int F$.}

The concept of {\it diameter} can be extended to arbitrary nonempty sets of points, if we replace $\max$ by $\sup$ in its definition and accept $\infty$ as a possible value. The preceding lemma enables us to prove an important relationship between the diameter of a figure and its supporting lines:

\theorem{3.15}{The diameter $d$ of a figure $F$ is attained by two points of $F$ and is the maximum of the distance between two parallel supporting lines.}
\proof{Let $\lscr
1$ and $\lscr
2$ be two parallel supporting lines at maximum distance, and let $a
1,a
2$ be the points where they touch $F$. Now suppose there were two points $p,q\in F$ such that $\seg{pq}>\seg{a
1a
2}$, and let $t
1$ and $t
2$ be the pair of supporting lines perpendicular to $pq$. Since the points $p$ and $q$ must be between these two lines, we have $\dist(t
1,t
2)>\seg{pq}>\seg{a
1a
2}=\dist(\lscr
1,\lscr
2)$, contradicting the choice of $\lscr
1$ and $\lscr
2$. It follows that $\seg{a
1a
2}$ is the maximum distance between two points of $F$, i.e. it is $d$.}

\digress{The {\it minimum} distance between a pair of distinct parallel supporting lines is called the {\it width} of a figure $F$. There is a curious analogue of Jung's theorem that relates the radius $r$ of the largest circle inscribed in a convex figure to its width $w$: it is known as {\it Blaschke's theorem} and says that $${w \over 3}\leq r \leq{w\over 2}.$$ The proofs are rather similar, except that in general the maximum inscribed circle is not unique.}

These concepts can be generalized to three and higher dimensions, where we have {\it supporting hyperplanes} that define {\it supporting half-spaces}. An outwards-pointing {\it normal vector} $d$ can be associated to a supporting hyperplane; the uniqueness of the latter for a given $d$ still holds, and theorem 3.15 generalizes nicely. The only concept that cannot be generalized is the orientation of the boundary of a convex figure, which can be defined only for unidimensional boundaries.

\sect{3.6. Convex bundles and separating lines.}

A {\it bundle} is a set of rays with a common origin. It is easy to see that a bundle is convex iff it falls in one of the following categories:\fig4\par
\hi  a) an empty set;\par
\hi  b) a single ray;\par
\hi  c) a pair of diametrically opposite rays;\par
\hi  d) an angle between 0 and $\pi$ (inclusive);\par
\hi  e) the whole plane.\par\vskip3pt plus5pt

Let $F$ be a (bounded) convex figure, and $p$ a point in the plane. It is not hard to prove that the {\it bundle subentended by $F$ from $p$}, that is, the set of all rays with origin $p$ that meet $F-\leftset 0 \rightset$, is a convex figure that contains $F$. It can be shown that a ray is interior to this bundle if and only if it passes through an interior point of the figure. The bundle can assume either form (d) or form (e) of the above list; case (e) happens if and only if $p$ is an interior point.\par

For an exterior or boundary point $p$, the angle $\alpha$ covered by the bundle can be anywhere between 0 (exclusive) and $\pi$ (inclusive). If $p$ is exterior (and $F$ is bounded), $\alpha$ will be strictly less than $\pi$. A boundary point $p$ is called a {\it corner} if $\alpha<\pi$, and an {\it ordinary point} otherwise. These facts allow us to prove another important property of convex figures:\par

\lemma{3.16}{For any point $p$ on the boundary of a convex figure $F$ there is at least one supporting line passing through $p$}
\proof{Consider the bundle $B$ subentended by $F$ from $p$.\fig4
Since $B$ is an angle not greater than $\pi$, the line $\lscr$ perpendicular to the bissecting line of $B$ and passing through $p$ is a supporting line for $B$. Since $F\subset B$, $\lscr$ contains no interior points of $F$, and therefore (by lemma 3.12) is also a supporting line for $F$.} 

A line $\lscr$ is said to {\it separate} two figures $F
1$ and $F
2$ if each of the closed half-planes determined by $\lscr$ contains one of the figures but not the other. If a separating line exists, then $F
1$ and $F
2$ can share at most boundary points; and, somewhat surprisingly, the converse also holds for convex figures. Before we can show this fact in general, we will prove it for convex bundles:\par

\lemma{3.17}{Two convex bundles $B$ and $C$ with common origin $p$ and nonempty, disjoint interiors admit a separating line.}
\proof{The conditions on $B$ and $C$ imply that both are angles between zero (exclusive) and $\pi$ (inclusive). Let $b
1$, $b
2$, $c
1$ and $c
2$ be their respective bounding rays, as they are found by going counterclockwise around $p$. Without loss of generality, we may assume that the angle between $b
2$ and $c
1$ (which may be zero) is smaller than that between $c
2$ and $b
1$.\par

\hp Consider the angle $b
2\pr c
1\pr$ opposite and equal to $b
2c
1$.\fig4 Since the bundles $B$ and $C$ each cover an angle at most $\pi$, $b
2\pr$ is not interior to $B$, and $c
1\pr$ is not interior to $C$. If $b
2\pr$ is also not interior to $C$, then the line $b
2b
2\pr$ is a separating line for $B$ and $C$. If $b
2\pr$ is interior to $C$, then $c
1\pr$ has to be exterior to $B$, otherwise the angle $b
1c
2$ would be smaller that $b
2c
1$. Then the line $c
1c
1\pr$ separates $B$ and $C$.}

\theorem{3.18}{Two convex figures $F
1$ and $F
2$ with disjoint interiors have a separating line.}
\proof{If the figures have disjoint interiors, it is easy to show that their only common points (if any) must be on their boundaries. Let's first consider the case in which the figures share a boundary point $p$ (or more than one). Consider the bundles $B
1$ and $B
2$ with origin $p$ and subentended by $F
1$ and $F
2$. Suppose these two bundles shared some internal ray $r$; then $r$ should pass through some point $q
1$ interior to $F
1$ and thru some $q
2$ interior to $F
2$.\fig4 The segments $pq
1$ and $pq
2$ would have some common point other than $p$ which would be interior to both figures, contradicting the hypothesis. Therefore, $B
1$ and $B
2$ share no interior rays, and have a separating line $\lscr$ by lemma 3.17, which also separates $F
1$ and $F
2$.\par

\hp Now let's consider the second case, namely $F
1$ and $F
2$ are disjoint. From the fact that the $F$'s are bounded and closed it can be shown that the set $\leftset \seg{p
1p
2}\relv p
1\in F
1\and p
2\in F
2\rightset$ has a minimum which is attained for two boundary points $p
1$ of $F
1$ and $p
2$ of $F
2$. Consider the lines $\lscr
1$ and $\lscr
2$ passing respectively through $p
1$ and $p
2$ and perpendicular to $p
1p
2$. These lines determine two disjoint half-planes $H
1$ and $H
2$, separated by a plane strip.\fig5
We claim that $F
1$ is contained in the half-plane $H
1$ (the one that does not contain $p
2$). To see why, suppose there is some point $q\in F
1$ that is not in $H
1$; then the whole segment $p
1q$ belongs to $F
1$ by convexity, and it is possible to find on it a point $p\pr$ closer to $p
2$ than $p
1$, a contradiction. Likewise, we can show that $F
2$ is contained in $H
2$, so both $\lscr
1$ and $\lscr
2$ (and any parallel line in between) separates the two figures.}

This result again generalizes to $k$-dimensional spaces, where a pair of convex figures with disjoint interiors have a {\it separating hyperplane}. It is also true for unbounded convex sets, but the proof given above breaks down (there may be no points that realize the minimum distance).

\sect{3.7. The convex hull.}

The {\it convex hull} of a set $P\subset\Sscr$, denoted by $\ch(P)$, is the smallest convex subset of $\Sscr$ that contains $P$. It is easy to show that $\ch(P)$ is the set of all points that can be expressed as a convex combination of points of $P$, and also the intersection of all convex subsets containing $P$. In fact, the following theorem (whose proof is lef to the reader) also holds:\par

\lemma{3.19}{The convex hull of a closed, non-empty and bounded subset $P$ of the plane is the intersection $H$ of all supporting half-planes of $P$.} 

These definitions are mathematically elegant, but are not very helpful in the development of practical algorithms for the determination of $\ch(P)$. In this chapter we will be particularly interested in the case when $P$ is a finite set of points $\leftset p
1, p
2, \ldotss, p
n\rightset$ in the plane, and it turns out that for this case we can give more useful definitions of the convex hull.\par

Imagine that we sweep the plane by a line perpendicular to a given unit vector $d$. There will be one or more of the points $\leftset p
1, p
2, \ldotss, p
n\rightset$ that will be encounterd last during this scan; they will be called the {\it extremal points along the direction $d$} (These points can also be defined as the intersection of $P$ with its supporting line perpendicular to $d$).\par

Let's repeat this process for all possible directions $d$, and in each case label the vector $d$ with the corresponding extremal point(s) of $P$ (If we draw the vectors $d$ from a fixed origin $O$, we can say that we are labeling points on the unit circle centered at $O$). Let's denote by $I
a$ the set of directions (or points in the unit circle) for which point $a\in P$ is extremal.\par

It is clear that $a$ is extremal along the direction $d$ iff $P$ is entirely contained in the closed half-plane defined by the line perpendicular to $d$ and passing through $a$. It follows that if $a$ is extremal along two dirctions $d
1$ and $d
2$, then $P$ is contained in the acute angle with vertex $a$ and sides perpendicular to $d
1$ and $d
2$. This implies the folowing properties of the sets $I
a$:\par

\lemma{3.20}{If a set $I
a$ contains two diametrically opposite points of the circle, then $P$ is contained in a straight line.}

\lemma{3.21}{If a set $I
a$ contains two directions $d
1$ and $d
2$ which are not diametrically opposite, then it contains all directions in the arc between $d
1$ and $d
2$.}

If we exclude the cases in which all points are collinear, the two lemmata above have the following consequences:

\lemma{3.22}{$I
a$ is either empty or is a closed connected arc less than $\pi$}
\proof{If $I
a$ is not empty, it has to be connected and less than $\pi$ by the preceding lemmata. Let $d$ be a limiting point of $I
a$ on the unit circle. Suppose $b$, but not $a$, were extremal along $d$. The line through $b$ and perpendicular to $d$ would not pass through $a$, and there would be some bundle of directions $\delta$ centered at $d$ for which $b$ occurs after $a$ in the scan.\fig4
This contradicts the limiting point assumption, so $d$ has to be in $I
a$.}

\lemma{3.23}{If $a$ and $b$ are distinct points of $P$, then $I
a\int I
b$ has at most a single point.}
\proof{If both $a$ and $b$ are extremal along some direction $d$, the segment $ab$ must be perpendicular to $d$. There are only two such $d$'s, which are diametrically opposite to each other. Since not all points are collinear, only one such direction $d$ can be in $I
a$, and therefore in the intersection.}

The following conclusion is the characterization we were seeking:

\theorem{3.24}{The convex hull of $P$ is the polygon $H$ with vertices $\leftset a\in P \relv \leftv I
a\rightv  >1\rightset$, taken in the order in which the corresponding arcs appear on the unit circle}
\proof{If $a,b$ are consecutive vertices of $H$, then $I
a$ and $I
b$ are consecutive arcs on the unit circle, and they have a common direction $d$. This means that the line perpendicular to $d$ passing through $a$ also passes through $b$ (i.e., supports side $ab$) and all other points of $P$ are on the same half-plane determined by this line. This proves that the polygon $H$ (the intersection  of those half-planes) is convex, contains all points of $P$, and therefore contains its convex hull.\par

\hp On the other hand, for each direction $d$ in any arc $I
a$ the supporting half-plane of $P$ whose normal is $d$ is delimited by the line through $a$ perpendicular to $d$, and this half-plane contains $H$. This implies that $H$ is contained in the convex hull of $P$ (lemma 3.19) and consequently is identical to it.}

Note that there is a kind of duality between the direction circle and the convex hull $H$. An arc in the circle is associated with a vertex of $H$, and, conversely, the junction of two arcs corresponds to an edge of $H$.  If we walk around the two objects in the same sense (say, counterclockwise), corresponding elements will be found to occur in the same order, and a ``step'' in one walk will correspond to a ``stop'' in the other.

\vfill\eject\end(635)