\documentclass[11pt,a4paper]{article}
\usepackage{amsmath}
%\usepackage{a4}
\usepackage{amsfonts}
\usepackage{graphicx}
\textwidth=15,1cm
\textheight=23,5cm
\hoffset = -17mm
\voffset = -15mm
\title{ADFOCS, Saarbr\"ucken %Fall School on Computational Geometry
\\Pseudotriangulations --- Exercises}
\author{G\"unter Rote}
\date{August 31 and September 1, 2005}

\newcommand{\olditem}{}
\let\olditem=\item
\newcommand{\oldenumerate}{}
\let\oldenumerate=\enumerate

% for latex:
\def\pdfdest #1 fitbh{}

\begin{document}
\maketitle
\begin{enumerate}
\def\item{{\count0=\value{enumi}\advance\count0 by 1 \edef\val{\the\count0}%
%    \message{FF\val FF}
        \pdfdest name {\val} fitbh}\olditem}
\def\enumerate{\let\item=\olditem\oldenumerate}

\item ($^\circ$3 points)
%\pdfdest name {1} fitbh
Prove that a pseudotriangulation with $x$ nonpointed and $y$ pointed vertices
has $e=3x+2y-3$ edges and $2x+y-2$ pseudotriangles.

(Can you find a three-line proof?)

\item (4 points) Consider the following conditions for a straight-line graph
 $G$ in the plane on
 a set $V$ of $n$ vertices, with a subset $V_p\subseteq V$ with $|V_p|=y$.
 \begin{tabbing}
\qquad \=\+
   (X)\quad \= The edges are non-crossing.
\\
   ($\ge$)\> There are at least $3n-y-3$ edges.
\\
   ($\le$)\> There are at most $3n-y-3$ edges.
\\
   (P)\> The vertices in $V_p$ are pointed.
\\
   (NP)\> The vertices in $V-V_p$ are nonpointed.
\\
   ($\Delta$)\> $G$ is non-crossing and decomposes the convex hull into pseudotriangles.
 \end{tabbing}
Show that the following sets of conditions are equivalent:
$$\hbox{(X)$\land$(P)$\land$($\ge$)} \iff \hbox{%
($\Delta$)$\land$(P)$\land$(NP)} \iff \hbox{%
($\Delta$)$\land$(P)$\land$($\ge$)} \iff \hbox{%
($\Delta$)$\land$(NP)$\land$($\le$)}$$
%
(Are there other subsets of the conditions which are equivalent to these?)


\item (3 points)
Find an efficient algorithm to test whether a given polygon
is a pseudotriangle [a convex polygon, a pseudoquadrangle].

\item (6 points) Suppose you have a pseudotriangulation of points which are
  moving.
Which conditions would you check to ensure that the graph remains a valid
  pseudotriangulation?

Compare the number of conditions that have to be monitored
for the case of a pointed pseudotriangulation and for the case of a triangulation.

 If the graph stops being a pseudotriangulation, which
  updates would you make in order to restore the pseudotriangulation?

%%%%%%%%%%%%% TANGENTS
\item ($^\circ$4 points)
A line $\ell$ through a vertex $v$ of a polygon $t$ is called \emph{tangent}
at $v$ if
\begin{enumerate}
\item $v$ is a corner of $t$ and $\ell$ crosses the boundary of $t$ at $v$
  from the interior to the exterior, or
\item $v$ is a reflex vertex of $t$ and $\ell$ does not cross the boundary of
  $t$ at $v$,
or
\item $\ell$ goes through one of the edges incident to $v$. (This is the limit
  case
of the other two cases.) \label{case-c}
\end{enumerate}
Through a given point $x$, there are always finitely many tangents of $t$.
For a pseudotriangle $t$, what are the regions of points $x$ for which
the number of tangents of $t$ is constant?
% Show that, for a pseudotriangle $t$,
% \begin{enumerate}
% \item through every interior point of $t$, there are exactly three tangent
%   lines, and
% \item through every point exterior to $t$, there is exactly one tangent line.
% \end{enumerate}

(optional) What is the situation for a pseudoquadrangle?

\item ($^\circ$3 points)
A \emph{bitangent} of a polygon $t$ is a line $\ell$ which is tangent to $t$ at two
positions, in the sense of the previous exercise
(where the two adjacent vertices in case (\ref{case-c}) count only as one tangency).

Show that a pseudoquadrangle has always exactly two bitangents.

\item (2 points)
Show that adding an edge interior of a pseudotriangle will always
create at least one new non-pointed vertex.

\item (4 points)
Find an efficient algorithm to triangulate a pseudotriangle.

\item (*6 points)
Let $T$ be a triangulation of a point set $S$ and let $P\subseteq T$ be a
pseudotriangulation of $S$.

Show that,
for every interior pointed vertex $v$ of $P$, one can select an edge of
$T-P$ which is incident to $v$ and lies in the reflex angle at $v$,
in such a way that each edge of $T-P$ is selected once. (In other words,
we have a \emph{perfect matching} between pointed vertices of $P$ and
edges of $T-P$.) (*2 points are for understanding the text of the exercise.)


(Is this matching unique? How many possibilities are there?)

\item
 A \emph{minimal} pseudotriangulation is a pseudotriangulation for which
  no proper subset of the edges forms a pseudotriangulation of the same point
  set.
  \begin{enumerate}
  \item (8* points)
If a pseudotriangulation contains no edge and no triangle whose
removal leaves a valid pseudotriangulation, then it is minimal.

(Hint: Use the previous exercise.)
\item (4 points)
Show that a minimal pseudotriangulation of $n\ge4$ points contains at most
  $3n-7$ edges.
\item ($6^*$ points)
(Can you show an upper bound of $3n-8$?)
  \end{enumerate}


%%%%%%%%%%%%%%%%% TUTTE SYSTEM

\item ($^\circ$7 points) Harmonic functions\\
Consider the following system of linear equations
\begin{eqnarray*}
  x_1 &=& 0.31\,x_2 + 0.43\,x_3 + 0.26 \,x_5\\
  x_2 &=& 13 \\
  x_3 &=& 0.6\,x_1 + 0.4\,x_5\\
  x_4 &=& 0.2\,x_3 + 0.7\,x_4 + 0.1 \,x_5\\
  x_5 &=& 15 \\
\end{eqnarray*}
There are two types of equations: (I) the coefficients on the
right-hand side are nonnegative and sum to~1 ($x_1,x_3,x_4$)
(B) The right-hand side is a constant ($x_2$ and $x_5$).
\begin{enumerate}
\item Prove that, in every solution $x$, there is always one of the
  type (B) variables which has the maximum (or minimum) value among
  all entries.  This statement remains true, whatever the constant
  values on the right-hand sides of type (B) equations are.
  
  (Under which conditions does this statement hold for a \emph{general}
  system of this form?)
\item Prove that there is at most one solution.  (Hint: Show that the
  difference $x-x'$ between two solutions $x$ and $x'$ solves a system
  with the same structure as the original system, and use part~(a).
\item Regard the system as an iteration procedure defining (``$:=$'')
  new values $x^{(\mathrm{new})}=x^{(k+1)}$ on the left-hand side in terms of
  previous values $x^{(\mathrm{old})}=x^{(k)}$ that are used on the right-hand
  side.  Start with $x_i^{(0)} := 0$ and prove by inducion that
  $x^{(\mathrm{new})}\ge x^{(\mathrm{old})}$ throughout the iteration.
\item Prove that this iteration converges, and the limit is a solution
  of the system.

\item (Prove that the solution depends monotonically on the right-hand
  sides of the type-B equations.)
\end{enumerate}


\item (2 points) \label{ex}
Write down the equilibrium equations, stating that every
  interior vertex lies at the center of gravity of its outneighbors,
  for the vertices of the following directed graph. The boundary
  vertices are fixed at the corners of the unit square $[0,1]^2$.
\begin{center}
  \includegraphics[scale=0.97]{../Bilder/exer-Tutte}
\end{center}

\item (4 points)
Let $a_1,\ldots,a_n$ be vectors in $\mathbb{R}^2$. Prove that
the system
$$ \sum_{i=1}^n \omega_i a_i = 0 $$
has a solution with $\omega_i>0$ if and only if the origin lies in
the relative interior of the convex hull of the points
$\{a_1,\ldots,a_n\}$.

\item (3 points)
Is the complete bipartite graph $K_{3,3}$ a Laman graph?
If so, construct a Henneberg construction for it.

\item (3 points)
Take the planar graph $G$ obtained by replacing an edge of $K_{3,3}$ by
another edge. Is this graph a Laman graph? Choose a plane embedding
for $G$, and construct a combinatorial pseudotriangulation for this
embedded graph.


\item (3 points)
Prove that a convex polygon has no expansive motion.

\item (2 points)
Write down the rigidity matrix $M$ of the graph of example~\ref{ex}, viewed as
  an undirected graph whose vertices lie on the grid
$\{0,1,2,3\}\times\{0,1,2,3\}$.

Write out the equations of the
system $M^T\omega=0$ for a vector $\omega=(\omega_{ij})$
indexed by edges $ij$.

%%%%%%%%%%%%%%%%% RECIPROCALS

\item (3 points) Construct the (essentially unique) reciprocal diagram of the following
  planar frameworks with a ruler alone (or with some geometry software like \textsc{Cinderella}).
  
\begin{center}
  \includegraphics[scale=0.9]%[width=\linewidth]
{../Bilder/exer-reciprocal}
\end{center}

Does the framework in (b) contain a pointed pseudotriangulation?


\item (12 points) Can a reciprocal of a given planar framework always be constructed
  with a ruler alone, i.~e., by drawing parallels and by intersecting lines.

\item (8 points)
Show that a planar framework with two linearly independent self-stresses always has a
self-stress for which the reciprocal is self-crossing.


\item (5 points)
Let $P$ be a simple polygon with $k$ convex vertices. Let $Q$ be a convex $k$-gon
whose vertices correspond to the convex vertices of $P$ in cyclic order.

Consider a triangulation $T_Q$ of $Q$. For every interior edge of $Q$ consider
the geodesic path (the shortest path inside $P$) between the corresponding
vertices of $P$. Show that the union of these geodesic paths generates a 
pointed pseudotriangulation inside $P$.

(Can every pointed pseudotriangulation of $P$ be generated in this way?)

\item (3 points) Find the highest locally convex functions over the following polygonal
  regions which remain below the given values at the marked points.
\begin{center}
  \includegraphics[width=0.95\linewidth]{../Bilder/exer-locally-convex}
\end{center}

\item (3 points)
Show that the piecewise maximum  of two locally convex functions
over the same domain is locally convex.

\item (10 points) Formulate the problem of finding the highest locally convex
  function over a polygonal domain, subject to upper bounds on the
values at certain points, as a linear programming problem.

\item (24 points) Set up the dual linear programming problem and find a
probabilistic, geometric, mechanical, or other intuitive interpretation for it.

% \item (3 points)
% For a seqment $pq$ in the plane, prove that
% $$\int\limits _{x\in pq} |x|^2\,ds
% = |p-q|^2 \cdot (|p|^2 + \langle p,q\rangle +|q|^2)
%  \cdot {\textstyle\frac 13}$$

\end{enumerate}

\end{document}

