Computational Geometry Column 43
The concept of pointed pseudo-triangulations is defined and a few of its applications described.
43.tex
\documentclass{article}
\usepackage{graphicx}
\usepackage{url}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{latexsym}

%\def\R{\mathbb{R}}
%\def\e{{\epsilon}}
%\def\a{{\alpha}}
%\def\b{{\beta}}

\newtheorem{theorem}{Theorem}

%Page dimesions: Unclear what should be used, so all commented out.
%\setlength{\oddsidemargin}{0in}
%\setlength{\topmargin}{-.5in}
%\setlength{\textwidth}{6.6in}
%\setlength{\textheight}{9in}

\title{Computational Geometry Column 43}
\author{%
Joseph O'Rourke\thanks{
Dept. of Computer Science, Smith Col\-lege, North\-ampton, 
MA 01063, USA.
orourke@\allowbreak cs.\allowbreak smith.\allowbreak edu.
Supported by NSF Distinguished Teaching Scholar Grant DUE-0123154.
}
}
\date{}
\begin{document}
\maketitle
%\pagestyle{empty}
%\thispagestyle{empty}

\begin{abstract}
The concept of pointed pseudo-triangulations is defined
and a few of its applications described.
\end{abstract}

A \emph{pseudo-triangle} is a planar polygon with exactly
three convex vertices.  Each pair of convex vertices is connected
by a reflex chain, which may be just one segment.  Thus, a triangle
is a pseudo-triangle.
A \emph{pseudo-triangulation} of a set $S$ of $n$ points in the plane
is a partition of the convex hull of $S$ into pseudo-triangles
using $S$ as a vertex set.
Under the name of ``geodesic triangulations,'' these found
use in ray shooting~\cite{cegghss-rspug-94},
and then for visibility algorithms by 
Pocchiola and Vegter~\cite{pv-cvgpt-95},
who named them (after a dual relationship to pseudoline arrangements)
and studied many of their properties~\cite{pv-ptta-96}.
Recently the identification of \emph{minimum pseudo-triangulations}
by Streinu~\cite{s-capnc-00} has generated a flurry of
new applications that we selectively sample here.

Minimum pseudo-triangulations have the fewest possible number of
edges for a given set $S$ of points.
The term \emph{pointed pseudo-triangulation} is gaining prominence
because of the following theorem\footnote{
	Thm.~3.1(2) of~\cite{s-capnc-00} (where the property is 
	called ``acyclicity'');
	Lem.~1 in~\cite{kkmsst-tdbpt-01}.
}
(see Fig.~\ref{pseudotri}):
\begin{theorem}
A pseudo-triangulation of $S$ is minimum iff
every point $p \in S$ is \emph{pointed} in the sense
that its incident edges span less than $\pi$
(i.e., they fall within a cone apexed at $p$ with aperture angle $< \pi$).
\end{theorem}

%Two pointed pseudo-triangulations of a set of $n=10$ points
%are shown in 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.7\linewidth]{pseudotri.eps}
%\fbox{pseudotri.eps}
\caption{Two pointed pseudo-triangulations of the same set of $n=10$ points.}
\label{pseudotri}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

Pointed pseudo-triangulations
have remarkable regularity in that each contains 
exactly $n-2$ pseudo-triangles.
In this they parallel triangulations of simple polygons and are unlike
triangulations of point sets, which may have from $n-2$ to $3(n-2)$ triangles.
% E = 3n - 3 - h; h >= 3.
Another indication of their well-behavedness
is the recent result~\cite{kkmsst-tdbpt-01}
that every set of $n$ points in general position
has a pointed pseudo-triangulation with maximum vertex degree
of $5$, a property not enjoyed by triangulations
(of either polygons or point sets).
This bounded degree may prove useful for designing data structures
employing pseudo-triangulations, such as those used for
collision detection~\cite{kss-kcdsp-02}.

We mention two disparate applications of pointed pseudo-triangulations.
Two years ago a long-standing open problem was settled
by Connelly, Demaine, and Rote when they proved that 
polygonal linkages cannot lock in the plane:
open
polygonal chains can be straightened, and closed polygonal
chains can be convexified~\cite{cdr-spacp-00}~\cite{o-cgc39-00}.
Their unlocking motions are \emph{expansive}: no distance
between any pair of vertices decreases.
Their proof relies on proving the existence of a solution to
differential equations describing this motion.
Although not difficult to solve numerically in practice,\footnote{
        \url{http://db.uwaterloo.ca/~eddemain/linkage/animations/}.
}
theirs does not constitute an algebraic proof.
This was provided by Streinu~\cite{s-capnc-00}.
She proved that a pointed pseudo-triangulation is rigid
when viewed as a bar and joint framework, and that
removal of a convex hull edge yields a mechanism with
one degree of freedom (1-dof) that executes an expansive motion.
Adding bars to a given collection of polygonal chains
to produce a pointed pseudo-triangulation,
and using a useful ``flipping'' property of pseudo-triangulations, leads 
ultimately to
a piecewise-algebraic straightening/convexifying motion.
%of $O(n^2)$ 
These 1-dof expansive motions have a rich structure that is just now
being elucidated~\cite{rss-emppp-01}.

Second, pointed pseudo-triangulations were used to make an
advance on an open problem posed by Urrutia~\cite{u-agip-00}:
%\cite{mo-cgc42-01}
Can a simple polygon of $n$ vertices be illuminated by
$c n$ interior $\pi$-floodlights placed at vertices,
with $c < 1$ (for sufficiently large $n$)?
For several years the lower bound on $c$ was $3/5$, but
no one could prove that $c$ was smaller than $1$.
Starting from a pointed pseudo-triangulation of the polygon,
Speckmann and T\'{o}th have recently established~\cite{st-vpgsp-01} that
$(2/3)n$ lights suffice,
finally breaking the $c=1$ barrier.\footnote{
        See \url{http://cs.smith.edu/~orourke/TOPP/}, Problem 23,
        for further developments.% on this problem.
}

We close with an open problem, posed in~\cite{rrss-ctpw-01}.
For a given set $S$ of points, let $\#T$ be the number
of triangulations of $S$, and $\#PPT$ be the number
of pointed pseudo-triangulations of $S$.
They conjecture that $\#T \le \#PPT$ for all $S$,
with equality only when the points of $S$ are in convex position.
This has been established for all sets of at most $9$ points~\cite{bkps-ceptg-01}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\small
\bibliographystyle{alpha}
\bibliography{43,/home1/orourke/bib/geom/geom}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}


\begin{enumerate}
\end{enumerate}

%10lines
see Fig.~\figref{X}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=\linewidth]{X.eps}
%\fbox{X.eps}
\caption{Z.}
\figlab{X}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End

43.bbl
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{KKM{\etalchar{+}}01}

\bibitem[BKPS01]{bkps-ceptg-01}
H.~Br{\"{o}}nnimann, L.~Kettner, M.~Pocchiola, and J.~Snoeyink.
\newblock Counting and enumerating pseudo-triangulations with the greedy flip
  algorithm.
\newblock September 2001.
  \url{http://www.cs.unc.edu/Research/compgeom/pseudoT/}.

\bibitem[CDR00]{cdr-spacp-00}
R.~Connelly, E.~D. Demaine, and G.~Rote.
\newblock Straightening polygonal arcs and convexifying polygonal cycles.
\newblock In {\em Proc. 41st Annu. IEEE Sympos. Found. Comput. Sci.}, pages
  432--442. IEEE, November 2000.

\bibitem[CEG{\etalchar{+}}94]{cegghss-rspug-94}
B. Chazelle, H.~Edelsbrunner, M.~Grigni, Leonidas~J. Guibas,
  J.~Hershberger, M.~Sharir, and J.~Snoeyink.
\newblock Ray shooting in polygons using geodesic triangulations.
\newblock {\em Algorithmica}, 12:54--68, 1994.

\bibitem[KKM{\etalchar{+}}01]{kkmsst-tdbpt-01}
L. Kettner, D. Kirkpatrick, A. Mantler, J. Snoeyink, B.
  Speckmann, and F. Takeuchi.
\newblock Tight degree bounds for pseudo-triangulations of points.
\newblock {\em Comput. Geom. Th. Appl.}, 2001.
\newblock To appear. Revision of abstract by L. Kettner, D. Kirkpatrick, and B.
  Speckmann, in \emph{Proc. 13th Canad. Conf. Comput. Geom.}, pp. 117-120,
  2001.

\bibitem[KSS02]{kss-kcdsp-02}
D. Kirkpatrick, J. Snoeyink, and B. Speckmann.
\newblock Kinetic collision detection for simple polygons.
\newblock {\em Internat. J. Comput. Geom. Appl.}, 2002.
\newblock To appear. Revised version of 
  \emph{Proc. 16th Annu. ACM Sympos.  Comput. Geom.}, pp. 322-330, 2000.

\bibitem[O'R00]{o-cgc39-00}
J.~O'Rourke.
\newblock Computational geometry column 39.
\newblock {\em Internat. J. Comput. Geom. Appl.}, 10(4):441--444, 2000.
\newblock Also in \emph{SIGACT News}, 31(3):47--49 (2000), Issue 116.

\bibitem[PV95]{pv-cvgpt-95}
M.~Pocchiola and G.~Vegter.
\newblock Computing the visibility graph via pseudo-triangulations.
\newblock In {\em Proc. 11th Annu. ACM Sympos. Comput. Geom.}, pages 248--257,
  1995.

\bibitem[PV96]{pv-ptta-96}
M.~Pocchiola and G.~Vegter.
\newblock Pseudo-triangulations: Theory and applications.
\newblock In {\em Proc. 12th Annu. ACM Sympos. Comput. Geom.}, pages 291--300,
  1996.

\bibitem[RRSS01]{rrss-ctpw-01}
D.~Randall, G.~Rote, F.~Santos, and J.~Snoeyink.
\newblock Counting triangulations and pseudotriangulations of wheels.
\newblock In {\em Proc. 13th Canad. Conf. Comp. Geom.}, pages 149--152, 2001.

\bibitem[RSS01]{rss-emppp-01}
G. Rote, F. Santos, and I. Streinu.
\newblock Expansive motions and the polytope of pointed pseudo-triangulations.
\newblock \url{http://cs.smith.edu/~streinu/Papers/polytope.ps}, September
  2001.

\bibitem[ST01]{st-vpgsp-01}
B. Speckmann and C.~D.~T{\'o}th.
\newblock Vertex $\pi$-guards in simple polygons.
\newblock December 2001.

\bibitem[Str00]{s-capnc-00}
I.~Streinu.
\newblock A combinatorial approach to planar non-colliding robot arm motion
  planning.
\newblock In {\em Proc. 41st Annu. IEEE Sympos. Found. Comput. Sci.} IEEE,
  November 2000.
\newblock 443--453.

\bibitem[Urr00]{u-agip-00}
J. Urrutia.
\newblock Art gallery and illumination problems.
\newblock In J.-R. Sack and J. Urrutia, editors, {\em
  Handbook of Computational Geometry}, pages 973--1027. North-Holland, 2000.

\end{thebibliography}
