\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}
\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input ../adgeomcs/mac.tex
\input ../adgeomcs/mathmac.tex
\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}
%
\begin{document}
\begin{center}
\fbox{{\Large\bf Fall, 2003 \hspace*{0.4cm} CIS 610}}\\
\vspace{1cm}
{Advanced geometric methods\\
\vspace{0.5cm}
Homework 1}\\[10pt]
September 30, 2003; Due October 21, beginning of class\\
\end{center}
You may work in groups of 2 or 3. Please, write up your
solutions as clearly and concisely as possible. Be rigorous!
You will have to present your solutions of the problems during
a special problem session.
\medskip
Instead of doing Problem B7, search the literature
for algorithms for computing the convex hull of a finite
set of points in the plane (or in space, but this is harder!).
Write a short critical paper presenting two
such algorithms. You will also have to give a presentation
during the problem session.
Some relevant sources are,
\medskip\noindent
{\sl Computational Geometry in C\/},
by O'Rourke, Joseph, Cambridge University Press,
1998, second edition, and
\medskip\noindent
{\sl Computational Geometry. Algorithms and Applications\/},
by Berg, M., Van Kreveld, M., Overmars, M., and
Schwarzkopf, O., Springer, 1997.
\medskip\noindent
{\sl Computational Geometry: An Introduction\/},
by F.P. Preparata and M.I. Shamos, Springer-Verlag, 1985.
\medskip
See also
\medskip\noindent
``Convex Hull Computations'', by Raimund Seidel,
in {\sl Discrete and Computational Geometry\/},
J. Goodman and J. O'Rourke, eds., CRC Press, pp. 361-375.
1997.
\vspace{0.5cm}
``A problems'' are for practice only, and should not
be turned in.
\vspace {0.5cm}\noindent
{\bf Problem A1.}
(a) Given a tetrahedron $(a, b, c, d)$, given any two distinct
points $x, y\in \{a, b, c, d\}$, let
let $m_{x,y}$ be the middle of the edge $(x, y)$.
Prove that the
barycenter $g$ of the weighted points $(a, 1/4)$, $(b, 1/4)$,
$(c, 1/4)$, and $(d, 1/4)$, is the common intersection of the
line segments $(m_{a, b}, m_{c, d})$, $(m_{a, c}, m_{b, d})$,
and $(m_{a, d}, m_{b, c})$. Show that if $g_d$ is the
barycenter of the weighted points $(a, 1/3), (b, 1/3), (c, 1/3)$
then $g$ is the barycenter of $(d, 1/4)$ and $(g_d, 3/4)$.
\vspace{0.5cm}\noindent
{\bf Problem A2}.
Given any two affine spaces $E$ and $F$,
for any affine map $\mapdef{f}{E}{F}$,
for any convex set $U$ in $E$ and any convex set $V$ in $F$,
prove that $f(U)$ is convex and that $f^{-1}(V)$
is convex. Recall that
$$f(U) = \{b \in F\ |\ \exists a\in U,\, b = f(a)\}$$
is the {\it direct image of $U$ under $f$\/}, and that
$$f^{-1}(V) = \{a \in E\ |\ \exists b\in V,\, b = f(a)\}$$
is the {\it inverse image of $V$ under $f$\/}.
\vspace{0.5cm}\noindent
{\bf Problem A3}.
Let $E$ be a nonempty set and $\affvec{E}$ be a vector space and assume that
there is a function $\mapdef{\Phi}{E\times E}{\affvec{E}}$, such that
if we denote $\Phi(a, b)$ by $\libvecbo{a}{b}$, the following properties
hold:
\begin{enumerate}
%\medskip
\item[(1)]
$\libvecbo{a}{b} + \libvecbo{b}{c} = \libvecbo{a}{c}$, for all $a, b, c \in E$;
%\medskip
\item[(2)]
For every $a\in E$, the map $\mapdef{\Phi_a}{E}{\affvec{E}}$ defined such that
for every $b\in E$,
$\Phi_a(b) = \libvecbo{a}{b}$, is a bijection.
\end{enumerate}
%\medskip
Let $\mapdef{\Psi_a}{\affvec{E}}{E}$ be the inverse of
$\mapdef{\Phi_a}{E}{\affvec{E}}$.
\medskip
Prove that the function $\mapdef{+}{E\times \affvec{E}}{E}$ defined such that
\[a + \novect{u} = \Psi_a(\novect{u})\]
for all $a\in E$ and all $\novect{u}\in \affvec{E}$ makes $(E, \affvec{E}, +)$ into
an affine space.
%\medskip
\medskip\noindent
{\it Note\/}:
We showed in class that an affine space $(E, \affvec{E}, +)$
satisfies the properties stated above. Thus, we obtain
an equivalent characterization of affine spaces.
\vspace {0.5cm}
``B problems'' must be turned in.
\vspace {0.25cm}\noindent
{\bf Problem B1 (30 pts).}
Given any two distinct points $a, b$ in $\affreal^2$ of
barycentric coordinates $(a_0, a_1, a_2)$ and $(b_0, b_1, b_2)$
with respect to any given affine frame,
show that the equation of the line $\lag a, b\rag$
determined by $a$ and $b$ is
\medskip
$$\detc{a_0}{b_0}{x}{a_1}{b_1}{y}{a_2}{b_2}{z} = 0,$$
\medskip\noindent
or equivalently
$$(a_1b_2 - a_2b_1)x + (a_2b_0 - a_0b_2)y + (a_0b_1 - a_1b_0)z = 0,$$
where $(x, y, z)$ are the barycentric coordinates of
the generic point on the line $\lag a, b\rag$.
\medskip
Prove that the equation of a line in barycentric coordinates is of the form
$$ux + vy + wz = 0,$$
where $u\not= v$, or $v\not= w$, or $u\not= w$.
Show that two equations
$$ux + vy + wz = 0\quad\hbox{and}\quad u'x + v'y + w'z = 0$$
represent the same line in barycentric coordinates iff
$(u',v', w') = \lambda (u, v, w)$ for some $\lambda\in\reals$
(with $\lambda\not= 0$).
\medskip
A triple $(u, v, w)$ where $u\not= v$, or $v\not= w$, or $u\not= w$,
is called a system of {\it tangential coordinates\/} of the line defined
by the equation
$$ux + vy + wz = 0.$$
\vspace{0.25cm}\noindent
{\bf Problem B2 (30 pts).}
Given two lines $D$ and $D'$ in $\affreal^2$ defined by tangential
coordinates $(u, v, w)$ and $(u', v', w')$ (as defined in problem B1),
let
\medskip
$$d = \detc{u}{v}{w}{u'}{v'}{w'}{1}{1}{1} =
vw' - wv' + wu' - uw' + uv' - vu'.
$$
\medskip
(a) Prove that $D$ and $D'$ have a unique intersection point
iff $d\not= 0$, and that when it exists,
the barycentric coordinates of this intersection point are
$$\frac{1}{d}(vw' - wv',\, wu' - uw',\, uv' - vu').$$
\medskip
(b) Letting $(O, i, j)$ be any affine frame for $\affreal^2$,
recall that when $x + y + z = 0$, for any point $a$, the vector
$$x\libvec{a}{O} + y\libvec{a}{i} + z\libvec{a}{j}$$
is independent of $a$ and equal to
$$y\libvec{O}{i} + z\libvec{O}{j} = (y, z).$$
The triple $(x, y, z)$ such that $x + y + z = 0$ is called the
{\it barycentric coordinates\/} of the vector $y\libvec{O}{i} + z\libvec{O}{j}$
w.r.t. the affine frame $(O, i, j)$.
\medskip
Given any affine frame $(O, i, j)$, prove that
for $u\not= v$, or $v\not= w$, or $u\not= w$,
the line of equation
$$ux + vy + wz = 0$$
in barycentric coordinates $(x, y, z)$
(where $x + y + z = 1$)
has for direction the set of vectors of barycentric
coordinates $(x, y, z)$ such that
$$ux + vy + wz = 0$$
(where $x + y + z = 0$).
\medskip
Prove that $D$ and $D'$ are parallel iff $d = 0$.
In this case, if $D\not= D'$, show that
the common direction of $D$ and $D'$ is defined by the vector
of barycentric coordinates
$$(vw' - wv',\, wu' - uw',\, uv' - vu').$$
\medskip
(c) Given three lines $D$, $D'$, and $D''$, at least two of which
are distinct,
and defined by tangential
coordinates $(u, v, w)$, $(u', v', w')$, and $(u'', v'', w'')$,
prove that $D$, $D'$, and $D''$ are parallel or
have a unique intersection point iff
\medskip
$$\detc{u}{v}{w}{u'}{v'}{w'}{u''}{v''}{w''} = 0.$$
\vspace{0.5cm}\noindent
{\bf Problem B3 (20 pts)}.
Given an affine space $E$ of dimension $n$ and an affine
frame $(a_0, \ldots, a_n)$ for $E$, let
$\mapdef{f}{E}{E}$ and $\mapdef{g}{E}{E}$ be two
affine maps represented by the two $(n+1)\times (n+1)$-matrices
$$\matta{A}{b}{0}{1}\quad\hbox{and}\quad \matta{B}{c}{0}{1},$$
w.r.t. the frame $(a_0, \ldots, a_n)$.
We also say that $f$ and $g$ are represented by
$(A, b)$ and $(B, c)$.
\medskip
(1) Prove that the composition $f\circ g$
is represented by the matrix
$$\matta{AB}{Ac + b}{0}{1}.$$
We also say that $f\circ g$ is represented by
$(A, b)(B, c) = (AB, Ac + b)$.
\smallskip
(2)
Prove that $f$ is invertible iff $A$ is invertible and that
the matrix representing $f^{-1}$ is
$$\matta{A^{-1}}{-A^{-1}b}{0}{1}.$$
We also say that $f^{-1}$ is represented by
$(A, b)^{-1} = (A^{-1}, -A^{-1}b)$.
Prove that if $A$ is an orthogonal matrix, the matrix associated with
$f^{-1}$ is
$$\matta{\transpos{A}}{-\transpos{A}b}{0}{1}.$$
Furthermore, denoting the columns of $A$ as $A_1, \ldots, A_n$,
prove that
the vector $\transpos{A}b$ is the column vector of components
$$(A_1\cdot b,\ldots, A_n\cdot b).$$
(where $\cdot$ denotes the standard inner product
of vectors)
\medskip
(3) Given two affine frame
$(a_0, \ldots, a_n)$ and
$(a_0', \ldots, a_n')$ for $E$,
any affine map $\mapdef{f}{E}{E}$
has a matrix representation $(A, b)$ w.r.t.
to $(a_0, \ldots, a_n)$ and
$(a_0', \ldots, a_n')$ defined such that
$b = \libvecbo{a_0'}{f(a_0)}$ is expressed over
the basis $(\libvecbo{a_0'}{a_1'},\ldots,\libvecbo{a_0'}{a_n'})$, and
$a_{i\, j}$ is the $i$th coefficient of
$f(\libvecbo{a_0}{a_j})$ over the basis
$(\libvecbo{a_0'}{a_1'},\ldots,\libvecbo{a_0'}{a_n'})$.
Given any three frames
$(a_0, \ldots, a_n)$,
$(a_0', \ldots, a_n')$, and
$(a_0'', \ldots, a_n'')$,
for any two affine maps $\mapdef{f}{E}{E}$ and
$\mapdef{g}{E}{E}$, if $f$ has the matrix representation
$(A, b)$ w.r.t.
$(a_0, \ldots, a_n)$ and
$(a_0', \ldots, a_n')$
and
$g$ has the matrix representation
$(B, c)$ w.r.t.
$(a_0', \ldots, a_n')$ and
$(a_0'', \ldots, a_n'')$, prove that
$g\circ f$ has
the matrix representation
$(B, c)(A, b)$ w.r.t.
$(a_0, \ldots, a_n)$ and
$(a_0'', \ldots, a_n'')$.
\medskip
(4) Given two affine frame
$(a_0, \ldots, a_n)$ and
$(a_0', \ldots, a_n')$ for $E$,
there is a unique affine map $\mapdef{h}{E}{E}$
such that $h(a_i) = a_i'$ for $i = 0, \ldots, n$,
and we let $(P, \omega)$ be its associated matrix representation
with respect to the frame $(a_0, \ldots, a_n)$.
Note that $\omega = \libvecbo{a_0}{a_0'}$, and that
$p_{i\, j}$ is the $i$th coefficient of
$\libvecbo{a_0'}{a_j'}$ over the basis
$(\libvecbo{a_0}{a_1},\ldots,\libvecbo{a_0}{a_n})$.
Observe that $(P, \omega)$ is also the matrix
representation of $\id_{E}$ w.r.t. the frames
$(a_0', \ldots, a_n')$ and
$(a_0, \ldots, a_n)$, {\bf in that order}.
For any affine map $\mapdef{f}{E}{E}$,
if $f$ has the matrix representation $(A, b)$ over the frame
$(a_0, \ldots, a_n)$ and
the matrix representation $(A', b')$ over the frame
$(a_0', \ldots, a_n')$, prove that
$$(A', b') = (P, \omega)^{-1}(A, b)(P, \omega).$$
\medskip
Given any two affine maps
$\mapdef{f}{E}{E}$ and $\mapdef{g}{E}{E}$, where
$f$ is invertible, for any affine frame
$(a_0, \ldots, a_n)$ for $E$, if
$(a_0', \ldots, a_n')$ is the affine frame image of
$(a_0, \ldots, a_n)$ under $f$ (i.e.,
$f(a_i) = a_i'$ for $i = 0, \ldots, n$),
letting $(A, b)$ be the matrix representation of
$f$ w.r.t. the frame $(a_0, \ldots, a_n)$ and
$(B, c)$ be the matrix representation of
$g$ w.r.t. the frame $(a_0', \ldots, a_n')$
({\bf not} the frame $(a_0, \ldots, a_n)$),
prove that $g\circ f$ is represented by the matrix
$(A, b)(B, c)$ w.r.t. the frame
$(a_0, \ldots, a_n)$.
\medskip
{\it Remark\/}:
Note that this is the {\bf opposite}
of what happens if $f$ and $g$ are both
represented by matrices w.r.t. the ``fixed'' frame
$(a_0, \ldots, a_n)$, where
$g\circ f$ is represented by the matrix
$(B, c)(A, b)$. The frame
$(a_0', \ldots, a_n')$ can be viewed as a ``moving'' frame.
The above has applications
in robotics, for example to rotation matrices
expressed in terms of Euler angles, or ``roll, pitch, and yaw''.
\vspace{0.5cm}\noindent
{\bf Problem B4 (20 pts)}.
Let $S$ be any nonempty subset of an affine space $E$.
Given some point $a\in S$,
we say that $S$ is {\it star-shaped with respect to $a$\/} iff
the line segment $[a, x]$ is contained in $S$ for every
$x\in S$, i.e. $(1 - \lambda)a + \lambda x \in S$
for all $\lambda$ such that $0\leq \lambda \leq 1$.
We say that $S$ is {\it star-shaped\/} iff
it is star-shaped w.r.t. to some point $a\in S$.
\medskip
(1) Prove that every nonempty convex set is star-shaped.
\medskip
(2) Show that there are star-shaped subsets that are not convex.
Show that there are nonempty subsets that are not star-shaped
(give an example in $\affreal^n$, $n = 1, 2, 3$).
\medskip
(3) Given a star-shaped subset $S$ of $E$, let $N(S)$ be the set of
all points $a\in S$ such that $S$ is star-shaped with respect to $a$.
Prove that $N(S)$ is convex.
\vspace{0.5cm}\noindent
{\bf Problem B5 (50 pts)}.
(a) Let $E$ be a vector space, and let $U$ and $V$ be two subspaces
of $E$ so that they form a direct sum $E = U \oplus V$.
Recall that this means that every vector $x \in E$ can
be written as $x = u + v$, for some unique
$u\in U$ and some unique
$v \in V$. Define the function
$\mapdef{p_U}{E}{U}$
(resp. $\mapdef{p_V}{E}{V}$) so that
$p_U(x) = u$ (resp. $p_V(x) = v$), where
$x = u + v$, as explained above.
Check that that $p_U$ and $p_V$ are linear.
\medskip
(b) Now assume that $E$ is an affine space (nontrivial), and let
$U$ and $V$ be affine subspaces such that
$\vector{E} = \vector{U} \oplus \vector{V}$.
Pick any $\Omega\in V$, and define
$\mapdef{q_U}{E}{\vector{U}}$
(resp. $\mapdef{q_V}{E}{\vector{V}}$, with $\Omega\in U$) so that
\[
q_U(a) = p_{\vecsmal{U}}(\libvecbo{\Omega}{a})
\quad(\hbox{resp.}\quad
q_V(a) = p_{\vecsmal{V}}(\libvecbo{\Omega}{a})),
\quad\hbox{for every $a\in E$}.
\]
Prove that $q_U$ does not depend on the choice of
$\Omega\in V$ (resp. $q_V$ does not depend on the choice of
$\Omega\in U$).
Define the map $\mapdef{p_U}{E}{U}$
(resp. $\mapdef{p_V}{E}{V}$) so that
\[
p_U(a) = a - q_V(a)\quad(\hbox{resp.}\quad
p_V(a) = a - q_U(a)),
\quad\hbox{for every $a\in E$}.
\]
Prove that $p_U$ (resp. $p_V$) is affine.
\medskip
The map $p_U$ (resp. $p_V$) is called the {\it projection
onto $U$ parallel to $V$ (resp. projection
onto $V$ parallel to $U$)\/}.
\medskip
(c) Let $(a_0, \ldots, a_n)$ be $n + 1$ affinely
independent points in $\affreal^n$, and let
$\Delta(a_0, \ldots, a_n)$ denote the convex hull
of $(a_0, \ldots, a_n)$ (an $n$-simplex).
Prove that
if $\mapdef{f}{\affreal^n}{\affreal^n}$ is an affine map
sending $\Delta(a_0, \ldots, a_n)$ inside itself, i.e.,
\[f(\Delta(a_0, \ldots, a_n))
\subseteq \Delta(a_0, \ldots, a_n),\]
then, $f$ has some fixed
point $b\in \Delta(a_0, \ldots, a_n)$,
i.e.,
\[f(b) = b.\]
{\it Hint\/}:
Proceed by induction on $n$.
First, treat the case $n = 1$. The affine map
is determined by $f(a_0)$ and $f(a_1)$, which
are affine combinations of $a_0$ and $a_1$.
There is an explicit formula for some fixed point of $f$.
For the induction step, compose $f$ with some
suitable projections.
\vspace{0.5cm}\noindent
{\bf Problem B6 (40 pts)}.
Let $A$ be a nonempty convex subset of $\affreal^n$.
A function $\mapdef{f}{A}{\reals}$ is {\it convex\/} if
\[f((1 - \lambda)a + \lambda b) \leq
(1 - \lambda) f(a) + \lambda f(b)\]
for all $a, b \in A$ and for all $\lambda \in [0, 1]$.
\medskip
(a) If $f$ is convex, prove that
\[f\biggl(\sum_{i\in I} \lambda_i a_i\biggr)
\leq \sum_{i\in I} \lambda_i f(a_i)\]
for every finite convex combination in $A$, i.e.,
any finite family $(a_i)_{i\in I}$ of points in $A$
and any family $(\lambda_i)_{i\in I}$ with
$\sum_{i \in I} \lambda_i = 1$ and $\lambda_i \geq 0$
for all $i\in I$.
\medskip
(b)
Let $\mapdef{f}{A}{\reals}$ be a convex function
and assume that $A$ is convex and compact and
that $f$ is continuous. Prove that $f$ achieves its maximum
in some extremal point of $A$.
\vspace{0.5cm}\noindent
{\bf Problem B7 (100 pts)}.
(a)
Let $A$ be any subset of $\affreal^n$. Prove that
if $A$ is compact, then its convex hull $\s{C}(A)$
is also compact.
\medskip
(b)
Give a proof of the following version
of Helly's theorem using Corollary 1.10 of the
notes on convex sets (Convex sets: A deeper look):
\medskip\noindent
{\em Given any affine space $E$ of dimension $\mdeg$,
for every family $\{K_1, \ldots, K_n\}$ of $n$ convex
and compact subsets of $E$,
if $n\geq \mdeg + 2$ and the intersection
$\bigcap_{i \in I} K_i$ of any $\mdeg + 1$ of the
$K_i$ is nonempty (where $I\subseteq \{1, \ldots, n\}$, $|I| = \mdeg + 1$),
then $\bigcap_{i = 1}^{n} K_i$ is nonempty.}
\medskip\noindent
{\it Hint\/}: First, prove that the general case
can be reduced to the case where $n = m + 2$.
\medskip
(c) Use (b) to prove Helly's theorem without
the assumption that the $K_i$ are compact.
\medskip\noindent
You will need to construct some nonempty
compacts $C_i \subseteq K_i$. For this,
you will need to prove that the convex hull of
finitely many points is compact.
\medskip
(d) Prove that Helly's theorem holds even if
the family $(K_i)_{I\in I}$ is infinite,
provided that the $K_i$ are convex and compact.
\vspace{0.5cm}\noindent
{\bf TOTAL: 290 points.}
\end{document}