5. Problems

Problem CC-1. Which of these subsets of R$^2$ are convex? (a) a single point, (b) a line, (c) the upper half plane $y \geq 0$, (d) a filled-in semicircle, (e) the whole plane, (f) the empty set. (Note: Any statement you make about ``all points of the empty set'' is true, since there are no counterexamples. For example, all points of the empty set are green.)

Problem CC-2. Which of these sets are convex? (a) in R, an interval $[a,b]$; (b) in R$^3$, the sphere $x^2 + y^2 + z^2 = 1$; (c) in R$^3$, the solid ellipsoid $x^2 + 2 y^2 + 3 z^2 \leq 1$.

Problem CC-3. In R$^2$, consider four points $P,Q,R,S$, one in each of the four quadrants. Must the origin be in their convex hull? If yes, explain why; if no, give an example.

Problem CC-4. (a) In R$^2$, is a line segment convex? (b) Is the answer the same in R$^3$?

Problem CC-5. Find an explicit example to show that a linear combination of points $c_1 P_1 + \dots + c_k P_k$ might not be in the convex hull of $\{P_1,\dots, P_k\}$

(a) if $c_i \geq 0$ for all $i$ but $c_1 + \dots + c_k \neq 1$;

(b) if $c_1 + \dots + c_k = 1$ but not all of $c_1,\dots, c_k$ are $\geq 0$.

(You may need to choose coordinate axes.)

Problem CC-6. As mentioned in Section , a barycentric combination is a linear combination in which the coefficients add to 1.

(a) Show that any translation preserves barycentric combinations. In other words, if $T($x$) =$   x$+$   b and $Q = c_1 P_1 + \dots + c_k P_k$ with $c_1 + \dots + c_k = 1$, then $T(Q) = c_1 T(P_1) + \dots + c_k T(P_{k})$.

(b) Show, conversely, that if a linear combination is preserved by all translations, or even by one nontrivial translation, then the linear combination is barycentric.

(c) Show that, in fact, if a linear combination is barycentric then it is preserved by all affine transformations. (Method: For $\Rightarrow$, use (a) and the observation that homogeneous linear combinations preserve all linear combinations, so for affine ...; for $\Leftarrow$, use (b) and the observation that translations are a particular kind of affine transformation.)

Problem CC-7. Prove that the image of a convex set under an affine transformation is convex. In other words, if $S$ is a convex subset of R$^n$ and $T:$   R$^n \rightarrow$   R$^m$ is an affine transformation, then the image $T(S)$ is also convex. (You may assume the fact that the image under an affine transformation of the line segment joining two given points is the line segment joining the images of those points. In other words, $T(\overline {PQ}) = \overline {T(P)T(Q)}$. To prove the statement, just try to apply the definition of a convex set to $T(S)$. Remember, every point in $T(S)$ is of the form $T(P)$ for some point $P$ in $S$.)

Problem CC-8. Use Problem CC- to show that the image of a convex set under an orthogonal or oblique projection is still convex.

Problem CC-9. Invent an example to show that a point in R$^2$ can be a convex combination of four given points in more than one way, i.e., with more than one list of coefficients.

Problem CC-10. Invent an example of a non-convex polyhedron that, when viewed with an orthographic projection, partially hides one of its own edges. (Your answer will be a sketch of the image. Use dotted lines to represent hidden parts of edges.)

Problem CC-11. Explain why the method of Section 5 is valid. (What does the sign of a dot product say about the angle between the two vectors?)

Problem CC-12. For the tetrahedron $P = (2,0,0)$, $Q = (0,3,0)$, $R = (0,0,4)$, $S = (1,1,1)$, which faces are visible from above by an orthographic projection, i.e., from the direction k$= (0,0,1)$? Use a computer method that would be valid for any tetrahedron.

Problem CC-13. (a) In testing visibility for the case of a finite viewpoint $V_0$, as in §4, we choose v$= V _ 0 - P _ 0$ and then look at the value of N$_ {out} \cdot$   v. Show that this value is the same if we use any $P _ i$ in place of $P_0$. (Method: To compare N$_ {out} \cdot (V _ 0 - P _ 0)$ with N$_ {out} \cdot (V _ 0 - P _ i)$, expand and subtract the two and then try to isolate the factor $P _ 0 - P _ i$.)

(b) There is a similar issue for N$\cdot$   w, where w$= Q - P _ 0$ with $Q$ being a test point not on the face. State what the issue is and show something similar to part (a).

Problem CC-14. Suppose $P$ and $Q$ are each a convex combination of $P _ 1,\dots, P_n$. Show that each point of the line segment joining $P$ and $Q$ is a convex combination of $P _ 1,\dots, P_n$. (Start from the definition of a convex combination, without quoting Theorem 3.1 or Theorem 3.2. Suggestion: To get an idea, try the case $n = 3$, first with some numerical coefficients and then with letters as coefficients.)

Problem CC-15. Show that any point $Q$ that is a convex combination of points $P _ 1,\dots, P_n$ can be obtained by constructing line segments repeatedly. More specifically, as a first stage construct the segment $\overline {P_1 P_2}$; as a second stage construct a segment from a point on the first segment to $P_3$; as a third stage construct a segment from a point on the second segment to $P_4$, and so on; the problem is to show that at stage $n-1$ you can get the desired point $Q$, if the line segments at each stage are chosen carefully.

Equivalently, show that any convex combination of $P _ 1,\dots, P_n$ is on a line segment from some convex combination of $P_1,\dots, P_{n-1}$ to $P_n$.

(Method for the case $n = 3$: For the point $Q = c_1 P_1 + c_2 P_2 + c_3 P_3$, with $c_i \geq 0$ and $c_1 + c_2 + c_3 = 1$, rewrite $Q$ as

$Q = (c_1 + c_2) ({\frac{\displaystyle c_1}{\displaystyle c_1 + c_2}} P_1 + {\frac{\displaystyle c_2}{\displaystyle c_1 + c_2}} P_2) + c_3 P_3$, or equivalently, as

$Q = (1-t)(c'_1 P_1 + c'_2 P_2) + t P_3$, for $t = c_3$ and suitable $c'_i$.

Why is this point on a line segment from a convex combination of $P_1$ and $P_2$ to $P_3$? It would be bad if the denominator were zero, but then $Q = P_3$, which is an easy case.)

Problem CC-16. Use Problem CC- and Problem CC- to prove Theorem 3.1.

(Method: For points $P _ 1,\dots, P_n$, let $H$ be the convex hull of the $P _ i$ and let $C$ be the set of all points that are linear combinations of the $P _ i$. You want to show that $H = C$. Do this by showing that $C \subseteq H$ ($C$ is contained in $H$, i.e., every point of $C$ is a point of $H$) and also that $H \subseteq C$. Explain how Problem CC- shows that $C$ is convex; since $C$ contains all the $P _ i$ (why?), $C$ contains the smallest convex set containing the $P _ i$, which is what? Explain how Problem CC- shows that any point of $C$ is contained in any convex set containing the $P _ i$, in particular, what?)

Problem CC-17. Prove Theorem 3.2, using any preceding exercises.

(Method: Do like Problem CC-, with suitably modified definitions of $H$ and $C$. The difference will be that in applying Problem CC-, the line segment will be between two convex combinations of different lists of points, but that's OK since the two lists can be merged into one longer list; in applying Problem CC-, even the list of $P _ i$ will depend on which $Q$ is used.)

Problem CC-18. A regular octahedron is a polyhedron with six vertices and eight faces, each an equilateral triangle. Consider the regular octahedron with vertices $(\pm 2, 0,0)$, $(0,\pm 2,0)$, and $(0,0,\pm 2)$. Find a face that is visible from $(3,3,3)$ but not from $(1,1,1)$. (You may use intuition to decide which face, but for your final answer use a method that is suitable for computer. See Figure .)

Figure: An octahedron

book/06dir/oct.eps

Problem CC-19. A regular icosahedron is a polyhedron with twenty sides, each an equilateral triangle. Five sides meet at each vertex. See Figure .

(a) How many vertices and how many edges does a regular icosahedron have? (Method: ``Overcount'' by counting each vertex [or edge] of each face separately, and then divide by the number of faces that each vertex [or edge] is on.)

A regular icosahedron can be made from a regular octahedron As follows: The ``golden ratio'' (a favorite number of the ancient Greeks) is the number $\rho = (1+\sqrt 5)/2 \approx 1.618034\dots$, which is the positive root of the equation $x ^ 2 = x + 1$. Take the regular octahedron described in Problem CC-. Each vertex of the icosahedron will be a point on the edge of the octahedron, dividing the edge in the ratio $\rho : 1$. Of course, there are two choices of such a point, and you need to choose just one.

(b) Give an example of such a vertex. (Method: Choose an edge, think of it as a line segment, and notice that the two choices involve $t = 1 / (\rho + 1)$ and $t = \rho/(\rho+1)$. But choose just one vertex.)

(c) Find two more such points, so that the three are on the three edges of one face of the octahedron.

(d) What is the length of each edge of the icosahedron?

(e) If you can, list all vertices.

Figure: An icosahedron

book/06dir/icos.eps

Problem CC-20. A regular dodecahedron is a polyhedron with twelve sides, each a pentagon. Three sides meet at each vertex. See Figure .

(a) How many vertices and how many edges does a regular dodecahedron have? (Do as in (a) of Problem CC-.)

The regular dodecahedron and regular icosahedron are dual to each other. This means that if you start with one of these shapes, and then take the center point of each face, those points make the vertices of the other shape.

(b) If you have done Problem CC- or if you have been provided with the solution to it, then you can construct a regular dodecahedron as the dual of the icosahedron. Find two vertices of this regular dodecahedron.

(c) What is the length of a side of the regular dodecahedron made this way?

Figure: A dodecahedron

book/06dir/dod.eps

Problem CC-21. In Problem CC-, (c) states that affine transformations preserve barycentric combinations. Show that, conversely, if a function $T:$R$^n \rightarrow$   R$^n$ preserves barycentric combinations then $T$ must be an affine transformation. (This is a strong statement, since $T$ is not stated to have any special property other than preserving barycentric combinations. Method: Let b$= T($0$)$ and show that the related function $U:$   R$^n \rightarrow$   R$^m$ is a homogeneous linear transformation, where $U($x$) = T($x$) - T($0$)$. Keep in mind the possibility of making a linear combination such as v$+$   w barycentric by rewriting it as v$+$   w$-$   0, where the coefficients add to 1.)

Problem CC-22. An interesting convex polyhedron is the rhombic dodecahedron, with twelve sides, each a rhombus, and fourteen vertices. (An important property of rhombic dodecahedra is that they can be stacked with no space between, just as cubes can.) One way to make one is to use vertices $(\pm 2, 0,0)$, $(0, \pm 2,0,)$, $(0,0,\pm 2)$, and $(\pm 1, \pm 1, \pm 1)$, as shown in Figure .

(a) Is the face with vertices $(2,0,0)$, $(1,1,1)$, $(0,0,2)$, $(1,-1,1)$ visible from the viewpoint $(3,5,-2)$? (Use a computer method.)

Figure: A rhombic dodecahedron

book/06dir/rhdodec.eps

(b) Explain how a rhombic dodecahedron can be obtained by taking the union of a suitable octahedron (Figure ) and a suitable cube, both centered at the origin, and then taking the convex hull. (You may use without proof the fact that the rhombic dodecahedron is convex, being the convex hull of its vertices.)

Problem CC-23. For any kind of polyhedron, the Euler characteristic (Euler = ``oiler''), is $V - E + F$, where $V$ is the number of vertices, $E$ is the number of edges, and $F$ is the number of faces.

(a) Find the Euler characteristics of a tetrahedron, cube, octahedron, dodecahedron (regular), icosahedron, and rhombic dodecahedron. (See various Figures.) They should all have the same value! (But indicate your computation in each case.)

(b) If you take a polyhedron and on some face draw a new edge between two vertices that are not already connected by an edge, what is the effect on the Euler characteristic?

(c) If you take a polyhedron and on some face make a new vertex (somewhere in the middle) and draw edges from it to the other vertices of the face, what is the effect on the Euler characteristic?

Actually, all polyhedra that are ball-like have the same Euler characteristic, and from (b) and (c) you can start to see why. In contrast, polyhedra that are like a torus (doughtnut-shaped) have a different Euler characteristic.