\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}}
\DeclareMathOperator{\im}{im}
\newcommand\Stack{\mathrm{Stack}}
\renewcommand{\to}{\longrightarrow}


\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}
\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 7}}
\vspace{15pt}

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

\vspace{20pt}
{\large\bf Problem 1: }\textit{Original references}\hfill (6 Points)\\[3pt]
In class we discussed theorems due to Ernst Sas, Alexander Macbeath, and György Elekes.
\begin{compactenum}[\normalfont (a)]
\item The theorem due to Ernst Sas (1939) reads as follows: \\
Let $C$ be a convex disk (a convex body in the plane) and let $n \geq 3$ be an integer. If $P_{(n)}$ is an $n$-gon of maximal area contained in $C$, and $P^2_n$ is a regular $n$-gon inscribed into the unit disk $B^2$, 
then 
\[
\frac{\mathrm{vol}(P_{(n)})}{\mathrm{vol}(C)}\ge\frac{\mathrm{vol}(P^2_n)}{\mathrm{vol}(B^2)}= \frac{n}{2\pi}\sin \frac{2\pi}{n},
\]
with equality if and only if $C$ is an ellipse.
\item The theorem due to Alexander Macbeath (1951) is an extension of this result: \\ 
Let $C$ be a convex body in $\R^d$ and let $n \geq d+1$ be an integer. If $P_{(n)}$ is a polytope with $n$ vertices of maximal volume contained in $C$, and 
$P^d_n$ is a  convex polytope of maximal volume inscribed into the unit ball $B^d$,  
then 
\[
\frac{\mathrm{vol}(P_{(n)})}{\mathrm{vol}(C)}\ge\frac{\mathrm{vol}(P^d_n)}{\mathrm{vol}(B^d)},
\]
with equality if and only if $C$ is an ellipsoid.
\item The theorem due to György Elekes (1986) reads as follows: \\ Let $P_{(n)}^d$ be a convex $d$-polytope with $n$ vertices contained in $B^d$. Then 
\[
\frac{\mathrm{vol} (P_{(n)}^d)}{\mathrm{vol}(B^d)} \le  \frac{n}{2^d}.
\]
\end{compactenum}
For each of the theorems above, find and properly cite the original reference and say a few words about the (original) proof.

\newpage

{\large\bf Problem 2: }\textit{Rectangular boxes}\hfill (8 Points)
\begin{compactenum}[\normalfont (a)]
\item For every convex body $C$ in $\R^d$ there is a rectangular $d$-box\footnote{A rectangular $d$-box is the $d$-fold Cartesian product of intervals.} $R$ 
with center $c$ and a constant $f(d) > 0$ that depends only on $d$ such that the inclusions 
\[
R-c\ \ \subseteq\ \ C - c\ \ \subseteq\ \ f(d) (R-c)
\]
hold.
\item Give good upper and lower bounds for $f(d)$.
\item What happens if we ask for axis-parallel rectangular boxes?
\end{compactenum}

\vspace{20pt}

{\large\bf Problem 3: }\textit{Guarantees}\hfill (6 Points)\\[3pt]
% Recall that a convex body in $\R^d$ is \Emph{well-guaranteed} if it is contained in a $d$-ball and contains a $d$-ball. 
Show that for convex bodies $C\subseteq B^d$ %contained in the unit $d$-ball centered at the origin
the following types of ``guarantees'' are equivalent:
%ow that, given suitable $r_0,w_0,v_0 > 0$, the following statements or ``certificates'' are equivalent:
\begin{compactenum}[\normalfont (a)]
\item $C$ contains a ball of radius $r_0$, for a specified $r_0 > 0$.
\item $C$ has width\footnote{The \Emph{width} of $C$ is defined as the minimal distance between two parallel supporting hyperplanes for $C$.} at least $w_0$, for a specified $w_0 > 0$.
\item $C$ has volume\footnote{By \Emph{volume} we mean the Lebesgue measure.} at least $v_0$, for a specified $v_0 > 0$.
\end{compactenum}
That is, show that from any such ``guarantee'' you can derive a guarantee for any of the two other types.
\end{document}