\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}