\documentclass[a4paper,12pt]{scrartcl}

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

\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{\cc}{\mathcal{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.3}

\selectlanguage{german}

\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, Marie Litz}
\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}

\vspace{20pt}
\centerline{\Large \bf{Discrete Geometry II -- Problem Sheet 1}}
\vspace{15pt}

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


\vspace{20pt}
{\large\bf Problem 1: }\textit{Simpleness assumption}\hfill (6 Points)\\
Let  $A \in \R^{n \times d}$ be a matrix with $n$ rows and $d$ columns. Let $b \in \R^n$ and $c \in \R^d$ be  vectors. Assume further that $A$ has no zero rows and has full rank $d$. We consider the linear program
\[
\mathrm{(P)}:\quad \begin{Bmatrix*}[r]
\max & c^t x & \\
& Ax & \le & b \\
& x & \geq & 0
\end{Bmatrix*}.
\]
Let $P \coloneqq \{ x \in \R^d \colon Ax \le b \}$ be the polyhedron of (P). We assume that $\dim P = d$. We call (P) \Emph{simple} if $P$ is simple. Let $\epsilon > 0$. If $b=(b_1, \ldots, b_n)^t$, then define $b_\epsilon \coloneqq (b_1 + \epsilon, b_2 + \epsilon^2, \ldots, b_n + \epsilon^n)^t$. Show that for a suitable, very small $\epsilon >0$, the resulting linear program $\mathrm{(P_\epsilon)}$ (obtained from (P) by replacing $b$ by $b_\epsilon$) is simple and still fulfills the same hypotheses as (P).

\vspace{20pt}

{\large\bf Problem 2: }\textit{How many vertices can $P$ have?}\hfill (6 Points)\\
Let (P) be as in Problem 1 above. % and assume additionally that (P) is simple. 

Use the Upper Bound Theorem for $d$-polytopes to derive good upper bounds for the number of vertices
of the polyhedron $P$. (Note that $P$ need not be bounded!)

How about lower bounds on the number of vertices of~$P$? 

\newpage

{\large\bf Problem 3: }\textit{Example: 2-$d$ linear interpolation}\hfill (8 (+2) Points)\\
Assume we are given $n$ data points $(x_1,y_1), \ldots, (x_n,y_n)$ in the plane, which we would like to approximate by
a line, that is, by an affine  function $f\colon \R \to \R$ of the form $x \mapsto ax + b$ for $a,b \in \R$.
% mapping $x_i$ to $y_i$. 

Construct a linear program to compute values $a$ and $b$ that minimize the ``$\ell_1$ error term''
\[
\sum_{i=1}^{n} |ax_i + b - y_i|.
\]
Construct a second linear program to compute values $a$ and $b$ that minimize the ``$\ell_\infty$ error term''
\[
\max_{1\le i\le n} |ax_i + b - y_i|.
\]

\emph{Note}: The ``usual'' way to approxiate is the $\ell_2$-approximation, which doesn't need linear programming.\\
\emph{Bonus:} Solve the two linear programs using a computer. For an online solver, see \href{http://www.phpsimplex.com/en/}{http://www.phpsimplex.com/en/}.
\end{document}


