\documentclass[a4paper,12pt]{scrartcl}

% \usepackage[english,german]{babel} % [verfuegbare Sprachen, letzgenannte ist aktiv]
\usepackage{tikz}
\usetikzlibrary{arrows,positioning} 

\usepackage{graphicx} % include eps graphics
\usepackage{psfrag} % .eps properly aligned, scaled, and rotated
\usepackage{wrapfig} % WRAP FIGURE [text umfliest das Bild]
\usepackage[ngerman,english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}
\usepackage{mathtools}
\usepackage{ngerman} % Silbentrennung ect. in neuer-Rechtschreibung-deutsch
\usepackage{eurosym} % Das euro Symbol [nicht mehr]
\usepackage{color} % textcolors [RGB oder auch 68 Standardfarben]
\usepackage{soul}
\usepackage{enumerate} % aufzaehlungen
\usepackage{paralist} % kuerzere Aufzaehlungen
\usepackage{url} % bessere Darstellung (hyperref: auch anklickbar)
\usepackage{alltt} % ermoeglicht uninterpretierten Text (sozusagen String)
\usepackage{ae,aecompl} % ecFonts auf cmFonts zurueckfuehren
\usepackage{ifthen}
\usepackage{amsmath} % MATH allignment[Matrix,Brueche,Gleichungen]
\usepackage{amssymb} % Mathe SYMBOLE
\usepackage{amsthm} % Mathe THEOREM [theorem,lemma,proof] Gliederung
\usepackage{verbatim} % multiline comment
\usepackage{paralist}
\parindent =0pt
\usepackage{geometry}
\graphicspath{{../../figures/}}
\geometry{
  body={},
  left=1.2in,
  right = 1.2 in,
  top=1.25in
}
\hypersetup{
  colorlinks = true,
  urlcolor = red,
  pdfauthor = {},
  pdfkeywords = {albert haase, mathematics, mathematik},
  pdfsubject = {},
  pdfpagemode = UseNone
}

\newcommand{\R}{\mathbb{R}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\s}{\mathbb{S}}
\newcommand{\su}{\mathcal{S}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ti}{\mathcal{T}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\dd}{\mathcal{D}}
\newcommand{\E}{\mathbf{E}}
\newcommand{\HRule}{\rule{1.03\textwidth}{0.5mm}}
\renewcommand\O{\mbox{\rm O}}
%\renewcommand{\subset}{\subseteq}
\newcommand{\V}{\mathcal{V}}
\newcommand\im{\operatorname{im}}
\newcommand\Stack{\mathrm{Stack}}
\renewcommand{\to}{\rightarrow}


\newcommand{\red}{\textcolor{red}} %Farben
\newcommand{\green}{\textcolor{green}}
\newcommand{\ink}{\textcolor[rgb]{0,.2,.8}}
\newcommand{\purp}{\textcolor[rgb]{0.9,0,.5}}
\newcommand{\sky}{\textcolor[rgb]{0,.5,.7}}
\newcommand{\tree}{\textcolor[rgb]{0,.4,.1}}
\newcommand\Emph[1]{\emph{\color{blue}#1}}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\VV}{\mathcal{V}}

\newcommand{\set}[1]{\ensuremath{ \left\{ #1 \right\}}}
\newcommand{\mset}[2]{\ensuremath{\left\{ #1  :  #2 \right\}}}
\renewcommand{\mapsto}{\longmapsto}
\newcommand{\inner}[1]{\left\langle \, #1  \,\right\rangle}
\newcommand{\linspan}[1]{\ensuremath{\text{span}\left\{ #1 \right \} }}
\newcommand{\ma}{\begin{smallmatrix} } \newcommand{\trix}{\end{smallmatrix}} % Matrix
\newcommand\aff{\operatorname{aff}}
\newcommand\conv{\operatorname{conv}}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\inter}{int}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\Cay}{Cay}
\newcommand{\M}{\mathcal{M}}
\newcommand{\B}{\mathcal{B}}
\linespread{1.2}

\selectlanguage{german}
\tikzset{
>=stealth',
pil/.style={
           ->,
           shorten <=1pt,
           shorten >=1pt,}
}

\begin{document}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushleft}
\includegraphics[scale=0.09]{bms-logo-eff}\\[5pt]
{\small Prof.~G\"unter M.~Ziegler} \\
{\small Albert Haase, Miriam Schlöter}
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushright}
\includegraphics[scale=0.4]{fu-logo}\\[5pt]
{\small Institut f"ur Mathematik }\\
{\small Arbeitsgruppe Diskrete Geometrie}\\
\end{flushright}
\end{minipage}

\enlargethispage{5mm}
\vspace{20pt}
\centerline{\Large \bf{Discrete Geometry II -- Problem Sheet 10}}
\vspace{15pt}

Please hand in your solutions to Prof.~Ziegler on \textbf{Tuesday, July~1, 2014} before the lecture begins. 

\vspace{30pt}

{\large\bf Problem 1: }\textit{Facet Volume and Polytope Volume}\hfill (8 Points)\\[3pt]
In the lecture we proved the equality
\[
v(b): =\vol_d(P_A(b)) = \frac{1}{d} \sum\limits_{i=1}^n \vol_{d-1} \big(F_i(P_A(b))\big) \cdot b_i.
\]
Here $A \in \R^{n \times d}$ for $n > d$ is a matrix with full rank and pairwise distinct row vectors that all have length one. The polytope 
\[
P_A(b) = \{ x \in \R^d : Ax \le b\},
\]
for $b \in \R^n$, has facets $F_i(P_A(b))$ with normal vector equal to the $i$-th column of $A$. The set of $b$-vectors for which $P_A(b)$ is non-empty is
\[
\B_A := \{b \in \R^n : P_A(b) \neq \emptyset \};
\]
the set of $b$-vectors that yield polytopes of volume at least $1$ is
\[
\M_A := \{ b \in B_A : \vol(P_A(b)) \geq 1\}.
\]

As an example, define the matrix
\[
A :=\frac{1}{\sqrt{2}}
\begin{pmatrix}
1 & 0 & 1 \\
0 & 1 & 1 \\
-1 & 0 & 1 \\
0 & -1 & 1 \\
0 & 0 & -\sqrt{2} \\
\end{pmatrix}.
\]
Choose a coordinate system ($=$ basis) for $\R^5 / \im(A) \cong \R^2$.
\begin{compactenum}[\normalfont (a)]
\item Sketch $\overline{\B_A}:= \B_A / \im(A)$ and $\overline{\M_A} := \M_A / \im(A)$.
\item Explicitly determine $\overline v: b \overset{\bar v}{\mapsto} v(b)$ as a piecewise polynomial function $\overline{\B_A} \to \R$.
\item Plot the function $\overline v$.
\item Is $\bar v$ differentiable on the interior of its domain $\B_A$? Twice differentiable?
\end{compactenum}



\newpage
{\large\bf Problem 2: }\textit{Volume of Minkowski Sum of Polytope and Scaled Ball}\hfill (6 Points)\\[3pt]
Let $P \subset \R^d$ be a $d$-dimensional polytope and let $B_d \subset \R^d$ be the unit ball. Define the function 
\[
f_P(t) := \vol_d(P + t B_d).
\]
\begin{compactenum}[\normalfont (a)]
\item For $d=2$ show that $f_P(t)$ is a polynomial of degree $2$ and give an interpretation of its coefficients.
\item Let $d=2$. Show that the Brunn--Minkowski inequality for $P$ and $B_2$ is equivalent to the ``isoperimetric inequality'' $p^2 \geq 4\pi a$, where $p$ is the perimeter and $a$ is the area of $P$.
\item Let $d=3$. Show that $f_P(t)$ is a polynomial of degree $3$ and interpret its coefficients.
\end{compactenum}

\vspace{20pt}

{\large\bf Problem 3: }\textit{Orthant-Shaped Polyhedra}\hfill (6(+2) Points)\\[3pt]
Let $a=(a_1, \dots, a_n) \in \R^d_{>0}$ have strictly positive coordinates and let $b \in \R^n_{\geq 0}$ have non-negative coordinates. Define the \Emph{orthant-shaped polyhedron} 
\[
Q(b) := \{ x \in \R^d : x \geq 0, \, a_i^t x \geq b_i \text{ for all } i=1,\dots,n\}.
\]
For $\alpha \in \R^n_{>0}$, define
\[
M := \{b \in \R^n_{\geq 0} : \vol_{d-1} F_i(Q(b)) \le \alpha_i \text{ for all } i=1,\dots,n \},
\]
where $F_i(Q(b))$ denotes the facet of $Q(b)$ with normal vector $a_i$.

\begin{compactenum}[\normalfont (a)]
\item Show that for $i=1, \dots, n$ and $\epsilon > 0$ 
\[
\vol_{d-1} \big(F_i(Q(b))\big) \le \vol_{d-1} \big(F_i(Q(b+\epsilon e_i))\big),
\]
where $e_i$ denotes the $i$-th unit vector in $\R^n$.
\item Show that there is a constant $c > 0$ such that $b_i \le c$ for all $ b\in M$.
\item Deduce from (b) that there is a constant $u > 0$ such that 
\[
P(b):= Q(b) \cap \{x \in \R^d: x_1 + x_2 + \dots + x_d \le u \}
\]
is a polytope such that $F_i(P(b)) = F_i(Q(b))$.
\item \emph{Bonus:} Show that $M$ is convex.
\end{compactenum}

\end{document}

