\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 Summer 1, 2009 \hspace*{0.4cm} CIS 610}}\\ \vspace{1cm} {\Large\bf Advanced Geometric Methods in Computer Science\\ Jean Gallier \\ \vspace{0.5cm} Homework 1}\\[10pt] May 28, 2009; Due June 4, 2009\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \vspace{0.5cm}\noindent {\bf Problem A1}. 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 A2}. 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.5cm}\noindent {\bf Problem B1 (10 pts).} (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.25cm}\noindent {\bf Problem B2 (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 B3 (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 B2), 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\libvecbo{a}{O} + y\libvecbo{a}{i} + z\libvecbo{a}{j}$$ is independent of $a$ and equal to $$y\libvecbo{O}{i} + z\libvecbo{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\libvecbo{O}{i} + z\libvecbo{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 B4 (40 pts)}. This problem uses notions and results from Problems B2 and B3. %, and \ref{pb2.8}. %\medskip In view of (a) and (b) of Problem B3, it is natural to extend the notion of barycentric coordinates of a point in $\affreal^2$ as follows. Given any affine frame $(a, b, c)$ in $\affreal^2$, we will say that the barycentric coordinates $(x, y, z)$ of a point $M$, where $x + y + z = 1$, are the {\it normalized barycentric coordinates\/} of $M$. Then, any triple $(x, y, z)$ such that $x + y + z\not= 0$ is also called a system of barycentric coordinates for the point of normalized barycentric coordinates \[ \frac{1}{x + y + z}\,(x, y, z). \] With this convention, the intersection of the two lines $D$ and $D'$ is either a point or a vector, in both cases of barycentric coordinates \[ (vw' - wv',\, wu' - uw',\, uv' - vu'). \] When the above is a vector, we can think of it as a point at infinity (in the direction of the line defined by that vector). \medskip Let $(D_0, D_0')$, $(D_1, D_1')$, and $(D_2, D_2')$ be three pairs of six distinct lines, such that the four lines belonging to any union of two of the above pairs are neither parallel nor concurrent (have a common intersection point). If $D_0$ and $D_0'$ have a unique intersection point, let $M$ be this point, and if $D_0$ and $D_0'$ are parallel, let $M$ denote a nonnull vector defining the common direction of $D_0$ and $D_0'$. In either case, let $(m, m', m'')$ be the barycentric coordinates of $M$, as explained at the beginning of the problem. We call $M$ the {\it intersection\/} of $D_0$ and $D_0'$. Similarly, define $N = (n, n', n'') $ as the intersection of $D_1$ and $D_1'$, and $P = (p, p', p'') $ as the intersection of $D_2$ and $D_2'$. \medskip Prove that %\medskip \[\detc{m}{n}{p}{m'}{n'}{p'}{m''}{n''}{p''} = 0\] % %\medskip\noindent iff either \begin{enumerate} \item[(i)] $(D_0, D_0')$, $(D_1, D_1')$, and $(D_2, D_2')$ are pairs of parallel lines; or \medskip \item[(ii)] the lines of some pair $(D_i, D_i')$ are parallel, each pair $(D_j, D_j')$ (with $j \not= i$) has a unique intersection point, and these two intersection points are distinct and determine a line parallel to the lines of the pair $(D_i, D_i')$; or \item[(iii)] each pair $(D_i, D_i')$ ($i = 0, 1, 2$) has a unique intersection point, and these points $M, N, P$ are distinct and collinear. \end{enumerate} \vspace{0.5cm}\noindent {\bf Problem B5 (20 pts)}. (a) Let $E$ be an affine space over $\reals$, and let $\linvec{a}{n}$ be any $n\geq 3$ points in $E$. Let $\linvec{\lambda}{n}$ be any $n$ scalars in $\reals$, with $\lambda_1 + \cdots + \lambda_n = 1$. Show that there must be some $i$, $1\leq i\leq n$, such that $\lambda_i\not= 1$. To simplify the notation, assume that $\lambda_1\not= 1$. Show that the barycenter $\lambda_1 a_1 + \cdots + \lambda_n a_n$ can be obtained by first determining the barycenter $b$ of the $n-1$ points $a_2, \ldots, a_n$ assigned some appropriate weights, and then the barycenter of $a_1$ and $b$ assigned the weights $\lambda_1$ and $\lambda_2 + \cdots + \lambda_n$. From this, show that the barycenter of any $n\geq 3$ points can be determined by repeated computations of barycenters of two points. Deduce from the above that a nonempty subset $V$ of $E$ is an affine subspace iff whenever $V$ contains any two points $x, y\in V$, then $V$ contains the entire line $(1 -\lambda)x + \lambda y$, $\lambda\in \reals$. \medskip (b) Assume that $K$ is a field such that $2 = 1 + 1\not= 0$, and let $E$ be an affine space over $K$. In the case where $\lambda_1 + \cdots + \lambda_n = 1$ and $\lambda_i = 1$, for $1\leq i\leq n$ and $n\geq 3$, in which case, we are dealing with a field of characteristic $p\geq 3$ and $p$ divides $n - 1$, show that the barycenter, $a_1 + a_2 + \cdots + a_n$, can still be computed by repeated computations of barycenters of two points. \medskip\noindent {\bf Extra Credit (20 points)\/}. Prove that even in the case where $K$ is a field of characteristic $2$ but $K$ has at least three distinct elements, the barycenter of any $n \geq 3$ points can be computed by repeated computations of barycenters of two points. \vspace{0.5cm}\noindent {\bf Problem B6 (30 pts)}. (i) Let $(a, b, c)$ be three points in $\affreal^2$, and assume that $(a, b, c)$ are not collinear. For any point $x\in \affreal^2$, if $x = \lambda_0 a + \lambda_1 b + \lambda_2 c$, where $(\lambda_0, \lambda_1, \lambda_2)$ are the barycentric coordinates of $x$ with respect to $(a, b, c)$, show that \[ \lambda_0 = \frac{\det(\libvecbo{x}{b}, \libvecbo{b}{c})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c})},\qquad \lambda_1 = \frac{\det(\libvecbo{a}{x}, \libvecbo{a}{c})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c})},\qquad \lambda_2 = \frac{\det(\libvecbo{a}{b}, \libvecbo{a}{x})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c})}. \] Conclude that $\lambda_0, \lambda_1, \lambda_2$ are certain signed ratios of the areas of the triangles $(a, b, c)$, $(x, a, b)$, $(x, a, c)$, and $(x, b, c)$. \medskip (ii) Let $(a, b, c)$ be three points in $\affreal^3$, and assume that $(a, b, c)$ are not collinear. For any point $x$ in the plane determined by $(a, b, c)$, if $x = \lambda_0 a + \lambda_1 b + \lambda_2 c$, where $(\lambda_0, \lambda_1, \lambda_2)$ are the barycentric coordinates of $x$ with respect to $(a, b, c)$, show that \[ \lambda_0 = \frac{\libvecbo{x}{b}\times\libvecbo{b}{c}} {\libvecbo{a}{b}\times\libvecbo{a}{c}},\qquad \lambda_1 = \frac{\libvecbo{a}{x}\times\libvecbo{a}{c}} {\libvecbo{a}{b}\times\libvecbo{a}{c}},\qquad \lambda_2 = \frac{\libvecbo{a}{b}\times\libvecbo{a}{x}} {\libvecbo{a}{b}\times\libvecbo{a}{c}}. \] Given any point $O$ not in the plane of the triangle $(a, b, c)$, prove that \[ \lambda_1 = \frac{\det(\libvecbo{O}{a}, \libvecbo{O}{x}, \libvecbo{O}{c})} {\det(\libvecbo{O}{a}, \libvecbo{O}{b}, \libvecbo{O}{c})},\quad \lambda_2 = \frac{\det(\libvecbo{O}{a}, \libvecbo{O}{b}, \libvecbo{O}{x})} {\det(\libvecbo{O}{a}, \libvecbo{O}{b}, \libvecbo{O}{c})}, \] and \[ \lambda_0 = \frac{\det(\libvecbo{O}{x}, \libvecbo{O}{b}, \libvecbo{O}{c})} {\det(\libvecbo{O}{a}, \libvecbo{O}{b}, \libvecbo{O}{c})}.\> \] \medskip (iii) Let $(a, b, c, d)$ be four points in $\affreal^3$, and assume that $(a, b, c, d)$ are not coplanar. For any point $x\in \affreal^3$, if $x = \lambda_0 a + \lambda_1 b + \lambda_2 c + \lambda_3 d$, where $(\lambda_0, \lambda_1, \lambda_2, \lambda_3)$ are the barycentric coordinates of $x$ with respect to $(a, b, c, d)$, show that \[ \lambda_1 = \frac{\det(\libvecbo{a}{x}, \libvecbo{a}{c}, \libvecbo{a}{d})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{d})},\>\> \lambda_2 = \frac{\det(\libvecbo{a}{b}, \libvecbo{a}{x}, \libvecbo{a}{d})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{d})},\>\> \lambda_3 = \frac{\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{x})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{d})}, \] and \[ \lambda_0 = \frac{\det(\libvecbo{x}{b}, \libvecbo{b}{c}, \libvecbo{b}{d})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{d})}. \] Conclude that $\lambda_0, \lambda_1, \lambda_2, \lambda_3$ are certain signed ratios of the volumes of the five tetrahedra $(a, b, c, d)$, $(x, a, b, c)$, $(x, a, b, d)$, $(x, a, c, d)$, and $(x, b, c, d)$. \medskip (iv) Let $(a_0, \ldots, a_\mdeg)$ be $\mdeg + 1$ points in $\affreal^\mdeg$, and assume that they are affinely independent. For any point $x\in \affreal^\mdeg$, if $x = \lambda_0 a_0 + \cdots + \lambda_\mdeg a_\mdeg$, where $(\lambda_0, \ldots, \lambda_\mdeg)$ are the barycentric coordinates of $x$ with respect to $(a_0, \ldots, a_\mdeg)$, show that \[ \lambda_i = \frac{\det(\libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_{i-1}}, \libvecbo{a_0}{x}, \libvecbo{a_0}{a_{i+1}}, \ldots, \libvecbo{a_0}{a_{\mdeg}})} {\det(\libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_{i-1}}, \libvecbo{a_0}{a_i}, \libvecbo{a_0}{a_{i+1}}, \ldots, \libvecbo{a_0}{a_{\mdeg}})} \] for every $i$, $1\leq i \leq \mdeg$, and \[ \lambda_0 = \frac{\det(\libvecbo{x}{a_1},\libvecbo{a_1}{a_{2}}, \ldots, \libvecbo{a_1}{a_{\mdeg}})} {\det(\libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_i}, \ldots, \libvecbo{a_0}{a_{\mdeg}})}. \] Conclude that $\lambda_i$ is the signed ratio of the volumes of the simplexes $(a_0, \ldots$, $x, \ldots a_\mdeg)$ and $(a_0, \ldots, a_i, \ldots a_\mdeg)$, where $0\leq i \leq \mdeg$. \vspace{0.5cm}\noindent {\bf TOTAL: 160 (+ 20) points.} \end{document} \vspace{0.5cm}\noindent {\bf Problem B7 (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 B8 (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.