10feb02.tex
% 10 Feb 02 lanl version
% figure files required: fg31.pstex, fg31.pstex_t, bigwrithe.eps
\documentclass[11pt]{article}

\usepackage{epsfig,amsmath,latexsym}
\usepackage{amsfonts,amssymb,graphicx}
\setlength{\textwidth}{6.2in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{.2in}
\setlength{\topmargin}{-0.25in}
\setlength{\headheight}{0in}

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{cor}[theorem]{Corollary}
%\newtheorem{defi}{Definition}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{prop}[theorem]{Proposition}
%\newtheorem{conj}{Conjecture}[section]

\def\binom#1#2{{#1}\choose{#2}}

\def\slfrac#1#2{\hbox{\kern.1em %
  \raise.5ex\hbox{\the\scriptfont0 #1}\kern-.11em %
  /\kern-.15em\lower.25ex\hbox{\the\scriptfont0 #2}}}

\newcommand{\ep}{\epsilon}
\newcommand{\pf}{\noindent{\bf Proof.~}}
\newcommand{\beq}{\begin{eqnarray}}
\newcommand{\eeq}{\end{eqnarray}}
\newcommand{\beql}[1]{\begin{eqnarray}\label{#1}}
\newcommand{\beqs}{\begin{eqnarray*}}
\newcommand{\eeqs}{\end{eqnarray*}}
\newcommand{\eqn}[1]{(\ref{#1})}

\newcommand{\qed}{{\Box}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\ds} {\displaystyle}
%\newcommand{\qed}{\square}
\newcommand{\RR}{{\mathbb{R}}}
\newcommand{\ZZ}{{\mathbb{Z}}}
\newcommand{\sG}{{\mathcal{G}}}
\newcommand{\sH}{{\mathcal{H}}}
\newcommand{\sS}{{\Sigma}}

\newcommand{\ba}{{\bf{a}}}
\newcommand{\bbb}{{\bf{b}}}
\newcommand{\bc}{{\bf{c}}}
\newcommand{\bd}{{\bf{d}}}

\newcommand{\bv}{{\bf{v}}}
\newcommand{\bw}{{\bf{w}}}
\newcommand{\bx}{{\bf{x}}}
\newcommand{\by}{{\bf{y}}}
\newcommand{\bz}{{\bf{z}}}

\newcommand{\bsq}{\vrule height .9ex width .8ex depth -.1ex}

\makeatletter
% put a period after section or subsection number in header
\def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth
      \def\@svsec{}\else
      \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi
      \@tempskipa #5\relax
       \ifdim \@tempskipa>\z@
         \begingroup #6\relax
           \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}%
         \endgroup
        \csname #1mark\endcsname{#7}\addcontentsline
          {toc}{#1}{\ifnum #2>\c@secnumdepth \else
                       \protect\numberline{\csname the#1\endcsname}\fi
                     #7}\else
         \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname
                       {#7}\addcontentsline
                            {toc}{#1}{\ifnum #2>\c@secnumdepth \else
                              \protect\numberline{\csname the#1\endcsname}\fi
                        #7}}\fi
      \@xsect{#5}}
% put a period after theorem and theorem-like numbers
\def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]}

\def\plain{plain}\ifx\fmtname\plain\csname fi\endcsname
      \def\batchfile{here.doc}
      \input docstrip
      \preamble

      Do not distribute the stripped version of this file.
      The checksum in the header refers to the documented version.

      \endpreamble
      \generateFile{here.sty}{t}{\from{here.doc}{}}
      \endinput
\fi
\ifcat a\noexpand @\let\next\relax\else\def\next{%
     \documentstyle[here,doc]{article}\MakePercentIgnore}\fi\next
\ifx\@Hxfloat\@Hundef\else\expandafter\endinput\fi
\let\@Hxfloat\@xfloat
\def\@xfloat#1[{\@ifnextchar{H}{\@HHfloat{#1}[}{\@Hxfloat{#1}[}}
\def\@HHfloat#1[H]{%
\expandafter\let\csname end#1\endcsname\end@Hfloat
\vskip\intextsep\vbox\bgroup\def\@captype{#1}\parindent\z@
\ignorespaces}
\def\end@Hfloat{\egroup\vskip \intextsep}

\makeatother

\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}

\catcode`\@=11
%\renewcommand{\section}{
%        \setcounter{equation}{0}
%        \@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
%        -.2ex}{2.3ex plus .2ex}{\large\bf}
%        }

\catcode`@=12

\thispagestyle{empty}

\begin{document}

\begin{center}
{\Large {\bf Affine Isoperimetric Inequalities for 
Piecewise Linear Surfaces}} \\
\vspace*{1.0\baselineskip}
{\em Joel Hass}\\
\vspace*{.2\baselineskip}
Department of Mathematics, \\
University of California, Davis \\
Davis, CA 95616 \\
\vspace*{1.5\baselineskip}

{\em Jeffrey C. Lagarias}\\
\vspace*{.2\baselineskip}
AT\&T Labs-Research, \\
Florham Park, NJ 07932-0971 \\
\vspace*{1.5\baselineskip}


%\today
(February 10, 2002)\\
\vspace*{1.5\baselineskip}
{\bf ABSTRACT}
\end{center}
We consider affine analogues of the isoperimetric 
inequality in the sense of piecewise linear (PL) manifolds.
Given a closed polygon $P$
having $n$ edges, embedded in $\RR^d$, we give upper
and lower bounds
for the minimal 
number of triangles $t$ needed to form a triangulated PL surface
embedded in $\RR^d$ having $P$ as its 
geometric boundary. More generally we
obtain such bounds for a triangulated 
(locally flat) PL surface having $P$ as its boundary
which is immersed in $\RR^d$ and whose interior is
disjoint from $P$. 
The most interesting case is dimension $3$. We use the
Seifert surface construction to show  that for any
polygon embedded in $\RR^3$ there exists
an embedded orientable triangulated PL surface
having at most $7n^2$ triangles, 
whose boundary is a subdivision of $P$. We complement
this with a construction of families of polygons
with $n$ vertices for which any such embedded surface requires at least
$\frac{1}{2}n^2 - O(n)$ triangles. It follows that  the 
(asymptotic) optimal combinatorial isoperimetric constant
in dimension $3$ lies between  1/2 and 7. We also
exhibit families of polygons in $\RR^3$
for which  $\Omega(n^2)$ triangles are required in any
immersed PL surface of the above kind.
In contrast, in dimension $2$ and in dimensions $d \ge 5$
there always exists an embedded locally flat  PL disk having
$P$ as boundary that contains at most $n$ triangles.
In dimension $4$ there 
always exists an immersed locally flat PL disk of
the  above kind that contains at most $3n$ triangles
An unresolved case is that of embedded PL surfaces in dimension
$4$, where we establish only an  $O(n^2)$  upper bound.

\vspace*{1.5\baselineskip}
\noindent
{\em Keywords:}
isoperimetric inequality, Plateau's problem,
computational complexity \\
\noindent {\em AMS Subject Classification:} Primary: 53A10 ~~
Secondary: 52B60, 57Q15 \\

%\setlength{\baselineskip}{1.5\baselineskip}
%
% Section 1
%

\section{Introduction}
\setcounter{equation}{0}

The classical isoperimetric inequality asserts
that for a simple closed curve $\gamma$ of length $L$ in $\RR^2$, the
area $A$ that it encloses satisfies
$$
A \le \frac{1}{4\pi} L^2,
$$
with equality only in the case of a circle.
This inequality generalizes to all higher dimensions, where we 
we allow either immersed surfaces, which can be restricted to be disks,
or embedded surfaces of arbitrary genus, as follows.
For a closed $C^2$-curve $\gamma$ of length $L$ embedded
in $\RR^d$ there exists an 
immersed disk of area $A$ as 
having $\gamma$ as boundary,
as well as an
embedded orientable surface of area $A$ having
$\gamma$ as boundary, such that in either case
$$
A \le \frac{1}{4\pi} L^2.
$$
The first of these results traces back to work of
Beckenbach and Rado~\cite{BR33}, while the second
result goes back to an argument of  Blaschke~\cite{Bla30}, according to
Osserman ~\cite[p. 1202]{Os76}. For general results see
Burago and Zalgaller ~\cite[Chapter 3]{BZ88}. 

In this paper we formulate discrete analogues of the 
isoperimetric inequality,
in the framework of piecewise linear (PL) manifolds. 
In the discrete analogue, the
boundary curve is a polygon $P$ in $\RR^d$, and the surface
is a  PL triangulated surface  having the polygon as
boundary. The discrete measure of ``length''
of the polygon is the
number of line segments $n$ in its boundary, and the discrete measure
of the ``area'' of a
triangulated surface is the number of triangles  $t$ that it contains.
This type of combinatorial minimal area problem is associated
to affine geometry because 
these discrete measures of ``length'' and ``area'' are both
affine invariant. That is, these problems are appropriately formulated
on $d$-dimensional affine space ${\mathbb A}^d$, rather than on
$\RR^d$ with its (extra) Euclidean structure; however in
what follows  we will denote the ambient space by $\RR^d$.

The discrete analogue has a simple answer 
in $\RR^2$, for one has the well known equality
$$
t = n - 2,
$$
in which $t$ is the number of triangles in any triangulation
of the (convex or nonconvex) polygon that adds no extra vertices,
see \cite[Theorem 23.2.1]{Su97}.
Such triangulations minimize the number of triangles 
over all triangulations, in which extra vertices may be added.
This bound is linear in the boundary length $n$, rather than
quadratic as in the classical isoperimetric inequality.

What happens in higher dimensions?
We consider two versions of the problem, corresponding
to the two versions of the classical isoperimetric problem
given above: 
the first is where the PL surface is an
embedded oriented surface with no restriction on its genus,  and the
second is where the surface is an immersed oriented
PL surface, usually taken to be
 a topological disk, with the extra restriction
that the interior of the surface cannot cut through its boundary.
More precisely, in the
second case we consider {\em complementary
immersed surfaces}, by which we mean immersed  surfaces 
(of any genus) whose interior
does not intersect its boundary, and whose boundary is
embedded \footnote{This condition rules out
a surface whose boundary is a multiple covering of 
the given boundary curve.}. Complementary
immersed surfaces allow extra freedom over embedded surfaces, 
but in dimension $d=3$ they still detect
knottedness; a polygon $P$ in $\RR^3$ has 
a complementary immersed surface that is a topological
disk if and only if $P$ is unknotted. 
Note that if we were to allow general immersed surfaces
rather than restricting to complementary immersed surfaces,
then the two-dimensional construction above works in all
higher dimensions, to produce an immersed disk
having $n-2$ triangles (whose interior in general will
intersect its boundary.) Thus in the case of general immersed surfaces
the discrete isoperimetric problem  has a trivial answer. 
With the extra restrictions above imposed
on the surfaces the answer becomes non-trivial.

In dimensions $d \ge 3$ we
show that there are qualitative affine isoperimetric
bounds, 
in which the exponent of the length function depends on the
dimension $d$.
More precisely, in the affine case the right side of the
bound is  proportional to
$O(L^2)$ in dimension $3$
and $O(L)$ in dimensions $d \ge 5$. In dimension $4$ we obtain
an $O(L)$ upper bound for complementary immersed PL disks.
The remaining case of
embedded PL surfaces in dimension $4$ we leave incompletely resolved,
obtaining  only an upper bound of $O(L^2)$. 

A variant of the construction of Seifert~\cite{Se34}
leads to the following
upper bound for oriented embedded surfaces.

\begin{theorem}~\label{upper-oriented}
For each closed polygonal curve
  $P$ with $n$ line segments embedded in $\RR^3$,
there exists an embedded oriented triangulated PL surface having a
PL subdivision of $P$ as boundary that has at most $7n^2$
triangles.
\end{theorem}

In this result, the polygonal curve $P$ is the geometric boundary
of the surface, but extra vertices may have to be added to
$P$ to get the boundary of the surface as a PL manifold.

Theorem~\ref {upper-oriented} shows that
for embedded surfaces of unspecified genus
the upper bound is polynomial in $n$. This result contrasts with bounds
for the size of an embedded oriented triangulated
PL surface of minimal genus spanning the curve $P$.
Hass, Snoeyink and Thurston~\cite{HST} show
in the unknotted case (minimal genus = $0$) that
$(C_1)^n$ triangles are sometimes required, for a fixed constant
$C_1 > 1,$ as $n \to \infty.$ Complementing this result,
Hass, Lagarias and Thurston \cite{HLT} show that in the
unknotted case there always exists an embedded minimal
genus PL surface (an embedded disk) spanning the curve $P$,
that contains  at most $(C_2)^{n^2}$ triangles, for a fixed constant
$C_2 > 1$. 




In \S3 we show that the upper bound of $O(n^2)$
in Theorem~\ref{upper-oriented} is the correct order
of magnitude. We present two constructions
based on different principles, giving $\Omega (n^2)$ lower bounds.

The first method involves the  genus $g(K)$ of the knot $K$.
The {\em genus} of a knot is the minimal genus of any orientable
embedded surface that has the knot as its boundary. The lower bound is
$$
t \geq 4g(K) + 1,
$$
and it applies to embedded orientable PL surfaces having  $K$
as boundary.
This lower bound depends only on the (ambient isotopy) type of the
knot $K$, so one gets the best result by minimizing the
number of edges in a polygon representing the knot, which
is called the {\em stick number} of the knot. Using
the $(n, n-1)$ torus knot,
we obtain the following result.

\begin{theorem}~\label{lower-oriented}
There exists an infinite sequence of values of $n \to \infty$
with  closed polygonal curves
  $P_n$ having  $n$ line segments embedded in $\RR^3$,
for which any
embedded triangulated PL surface, that is oriented and
that has a PL
subdivision of $P_n$ as boundary, requires at least
$\frac {n^2}{2} - 3n + 5$ triangles.
\end{theorem}


The second method uses an invariant of a knot diagram $K$,
the {\em writhe} $w(K)$. The lower
bound is
\begin{equation}~\label{wrbound}
t \geq  |w(K)|,
\end{equation}
and it applies to complementary immersed surfaces.
The writhe
is not an ambient isotopy invariant, but is an invariant of a
stronger equivalence relation, called {\em  regular isotopy},
on knot diagrams.
Regular isotopy is equivalence under Reidemeister moves of types II
and III only, with type I moves forbidden.


We apply this bound to show that there is
an infinite family of polygonal curves $P_n$ in $\RR^3$ having  a
quadratic lower bound for the number of triangles in
a  complementary immersed surface, of unrestricted genus. 

\begin{theorem}~\label{lower-oriented2}
There exists an infinite sequence of 
closed polygonal curves
  $P_n$ in $\RR^3$ having  $n$ line segments, with 
values of $n \to \infty$,
for which any
complementary immersed  triangulated PL surface
that has a PL
subdivision of $P_n$ as boundary, requires at least
$\frac {n^2}{36}$ triangles.
\end{theorem}

The writhe bound \eqn{wrbound} implies that a polygonal knot that
has a large writhe in one direction must have a large number
of crossings in any projection direction (Theorem~\ref{large.writhe}).

An interesting question concerns what is 
the best possible isoperimetric constant 
in Theorem~\ref{upper-oriented}, as $n \to \infty$.
There is a separate isoperimetric constant 
$\gamma_n$ for each $n \ge 3,$
given by
$$ 
\gamma_n = \max_{P_n} \left( \min_{\Sigma ~\mbox{spans}~ P_n} 
~\frac{1}{n^2} t(\Sigma) \right),
$$
in which $P_n$ runs over all polygons with $n$ edges embedded in $\RR^3$.
We define the 
 {\em asymptotic isoperimetric constant} $\gamma$ to be
$$ 
\gamma := \limsup_{n \to \infty}  \gamma_n. 
$$
Combining Theorems~\ref{upper-oriented} and
\ref{lower-oriented}
 implies that the asymptotic isoperimetric
constant must lie somewhere between 1/2 and 7.


In \S4 we consider the
combinatorial isoperimetric
problem for embeddings of a curve in
dimensions $d \geq 4$. We obtain two
$O(n)$ upper bounds.
In these dimensions we construct  PL surfaces
spanning the polygon which are locally flat,
as defined at the beginning of \S4.
The local flatness condition is
a restriction on how the surface is situated in $\RR^d$.
It is known that local flatness always holds for an
embedded PL surface in codimension $3$ or more
(see \cite[Corollary 7.2]{RS82}), hence requiring local flatness
puts a constraint only in 
dimension $d=4$. 

We first treat dimension $d=4$, and construct a 
complementary immersed surface
that is locally flat and has $O(n)$ triangles.

\begin{theorem}~\label{four.dim}
Let $P$ be a closed polygonal curve
 embedded in $\RR^4$ 
consisting of $n$ line segments.
Then there exists a complementary immersed triangulated PL disk,
which is locally flat, has $P$ as its PL boundary, 
and contains  $3n$ triangles.
\end{theorem}

Second, in dimensions $d \ge 5$,
by coning the polygon $P$ to a suitable
point we obtain 
an  embedded PL disk with $n$ triangles, 
which is automatically locally flat.


\begin{theorem}~\label{higher.dim}
Let $P$ be a closed polygonal curve
embedded in $\RR^d$,
with $d \ge 5$, consisting of $n$ line segments.
Then there exists an embedded triangulated PL disk
which is locally flat,  has
$P$ as its PL boundary, and  contains $n$ triangles.
\end{theorem}

These results establish that the complexity of
the spanning surface is $O(n^2)$ in dimension $3$,
and is $O(n)$ in all other dimensions, except 
possibly in dimension $4$ for embedded surfaces.
The increased complexity in  dimension $3$
might be expected, in that dimension $3$ is the only
dimension in which knotting is possible for curves.
As far as we know, the  remaining unresolved
case of embedded surfaces in
$\RR^4$ might conceivably have superlinear complexity;
if so, this would represent a new phenomenon
peculiar to the discrete case.
For this case we establish only an
$O(n^2)$ upper bound, as explained at the
end of \S5, while an $\Omega(n)$ lower bound is
immediate.

A further direction for PL
isoperimetric problems
would be to establish isoperimetric bounds for
higher-dimensional submanifolds.
Consider a $k$-dimensional triangulated closed
PL-manifold $M$ embedded in $\RR^d$, where $k \geq 2$,
and ask: what is  the minimal number of $(k+1)$-simplices in an
embedded triangulated PL $(k+1)$-dimensional manifold
having a PL-subdivision of $M$ as its boundary?

Earlier work on  the complexity of embedded surfaces bounding 
unknotted curves in $\RR^3$ under
various restrictions includes Almgren and Thurston~\cite{AT77}.
Connections between combinatorial
complexity of such surfaces and the computational complexity 
of problems in knot theory appear in  \cite{HL}, \cite{HLP}.


%
% Section 2
%

\section{Upper Bound}
\setcounter{equation}{0}

We establish Theorem~~\ref{upper-oriented} by using
a version of the construction of Seifert~\cite{Se34} of
an orientable surface having a given knot as boundary.
A general description of Seifert surfaces and their construction
appears in  Rolfsen~\cite[Chapter 5]{Ro76}. \\

\noindent{\bf Proof of Theorem~\ref{upper-oriented}:}
Given a closed polygon $P$ in $\RR^3$ having $n$ line
segments, we first choose an orientation for it.
We obtain a knot diagram by orthogonally
projecting it onto a plane. Fix once and
for all  a projection direction
in ``general position'', so that  the projections of
any two line segments in $P$ intersect in at most one
point, and if the two segments in $P$ are disjoint
then this point must correspond to interior points of the
two segments. Without loss of generality we may rotate the
polygon so that the projection direction is in the $z$-direction
and the projected plane is $z= 0$, and we may translate it in
the $z$-direction so that it lies in the half-space $z \geq 1.$
The  projected image of the polygon in the plane
has $n$ vertices and $c$ crossing
points, where
$$
c \le n(n-3)/2,
$$
since an edge cannot intersect
its two adjacent edges or itself.
We make the projection
into a planar graph by marking vertices at each crossing point,
which we call {\em crossing vertices}.
This graph is a directed graph, with directed edges
obtained by projection of the orientation assigned to
the polygonal knot $P$, and is regarded as sitting in
the plane $z= 0$. Each vertex of this planar graph has either two
or four edges incident on it, so the faces of the graph can
be two-colored; call the
colors white and black.  The graph has
a single unbounded face, which we consider colored white;
it also  at least one  bounded region colored black.
  We denote this
directed colored graph $\sG$; it has $n + c$ vertices, which
we call {\em initial vertices} in what follows.

We now add new vertices
to this graph as follows: At each edge containing
a crossing vertex we insert new vertices
very close to each of its crossing vertex
endpoints; call these {\em interior vertices}.
The resulting graph has $n + c$ {\em initial vertices} and
$4c$ interior vertices.  Each crossing vertex
has four edges incident to it.

Near each crossing vertex we now add edges
connecting pairs of interior vertices on adjacent
edges in cyclic order around the crossing point.
There are four such edges which
form a small quadrilateral enclosing the crossing vertex.
We choose the interior points close enough to the
crossing vertex so that the interior
of each edge in the boundary of this quadrilateral
does not intersect any other edge of the graph, and so
lies entirely inside one of the colored polygons of the original
graph. We assign that color to the edge. These four edges form two 
white edges and two black
edges; we discard the black edges and add the two white edges only, to form
an augmented planar graph.

The example of the
trefoil knot is pictured in Figure~\ref{trefoil.fig}; part (b) shows
the added vertices of the augmented planar graph, and the white
edges are indicated by dotted lines in (b).


\begin{figure}[hbtp]~
%\centering
%\input fg31.pstex_t
%\includegraphics[width=.7\textwidth]{fg31.pstex}
\begin{center}
\input fg31.pstex_t
\end{center}
\caption{Trefoil knot}
\label{trefoil.fig}
\end{figure}

The added white-colored
edges create two white-colored triangular regions adjacent
to each crossing vertex, which together form a ``bow-tie'' shaped region.
If one now deletes all crossing vertices and the four edges incident to
them (which have as other endpoint an interior vertex), and adds
in the white-colored edges only, then one obtains a new planar graph
$\sG'$, that has $n + 4c$ vertices.
This new graph may be disconnected, and consists of a union
of simple closed polygons.
  Its regions are
  two-colorable, with the coloring
obtained from that of $\sG$ by changing the color of the bow-tie
shaped regions from white to black.
%[[reference???]]
For the trefoil knot this is pictured in Figure~\ref{trefoil.fig} (c).

The graph $\sG'$
is a union of simple closed curves which we call {\em circuits},
some of which may be
nested inside others. To each circuit we assign an integer
level that measures its nesting.
An {\em innermost circuit} is one that contains
no other circuit: we assign  these innermost circuits level 0. We
now inductively define a level for each other circuit, to be
one more than the maximal level of any circuit they contain.
The maximal level that may occur is $n$.

We now construct a triangulated
embedded spanning surface $\Sigma$ for $\gamma$ as follows.

(1) For each circuit  of level $k$ we make a copy of this
circuit in the plane $z = -k,$ i.e. we translate it
from the plane $z= 0$ by
the vector $(0, 0, -k)$. It forms a simple closed polygon
that will form part of the surface $\sS$. If it has $m$ sides,
then we may triangulate it using $m - 2$
triangles lying in the plane $z= -k$.

(2) We next add vertical faces connecting the circuit $S$ to
the points of $\gamma$ lying above it. To do this we
first augment $\gamma$ by adding new vertices on $\gamma$
  corresponding to the boundaries of the
white edges constructed in $\sG'$. Above each endpoint of a
white edge there is a unique point on $\gamma$, which we
add as a new vertex. We also  add
new edges (not on $\gamma$) connecting these points. Call the
resulting augmented one-dimensional simplicial complex $\gamma'$. To each
edge of the circuit there is a unique edge of
$\gamma'$ that projects vertically onto it.
We take the convex hull of these two edges, that forms
a trapezoid with two vertical edges, plus the two edges
we started with.
These trapezoids will form part of the surface $\sS$.
Each of them may be triangulated by adding a diagonal
to the trapezoid.

(3) Above each bow-tie shaped region of $\sG'$ containing
a crossing vertex and two white edges, there lie four
edges of $\gamma'$, two edges of which
project to the white edges on the plane $z=0$,
and the other two of which are part of edges of
$\gamma$  whose projections on the
plane $z =0$ are disjoint except
at the crossing vertex. Let the vertices of the two
edges of $\gamma'$ lying above the
white edges be labelled $[\bx_1, \bx_2]$ and $[\by_1, \by_2]$
respectively, with the black edges (not part of $\gamma'$)
being $[\bx_1, \by_2]$
and $[\bx_2, \by_1]$,
and with the line segments $[\bx_1, \by_1]$
and  $(\bx_2, \by_2)$ being part of the original curve $\gamma$.
We then form the two triangles
$[\bx_1, \bx_2, \by_1]$ and $[\bx_2, \by_1, \by_2]$,
that share a common black edge $[\bx_2, \by_1]$, and add them to $\Sigma.$

We claim that $\Sigma$ forms a triangulated surface embedded in $\RR^3$,
which is orientable and has a
subdivision of $\gamma$ as its boundary.

To see that $\sS$ is embedded in $\RR^3$, note that
the triangulated pieces (1)-(3) of  $\sS$  are embedded, and when projected
to the $z$-axis have disjoint interiors.
Thus these pieces can only overlap along
their boundary edges.

We recall Seifert's argument to show $\sS$ is orientable; the contribution of
(1) and (2) corresponding to each circuit is a bowl-shaped surface
that is topologically a disk, with the crossing points located
near the lip of the bowl. At each crossing point the bowl is
attached to another bowl by a rectangular strip with a half-twist
in it, twisting through an angle of $\pi$.  Since it is constructed
from disks attached along boundary intervals, $\sS$ is topologically
a $2$-manifold with boundary. In addition, the construction connects a
bowl at level $j$ only to bowls at level $j \pm 1$.
A compatible orientation then takes as
one side the upper (inside) surface of bowls at level $2j$ and
the lower (outside) surface of bowls at level $2j + 1$, plus
corresponding sides of the strips connecting them.  So $\sS$ is orientable.

We now give an upper bound for the number of
triangles in $\sS$. The totality of triangles produced in
step (1) above is at most the number of
edges in all the
circuits; this
is at most the number
of edges in $P$ after adding internal vertices, and is at most $n + 4c$.
In step (2)
each trapezoid is associated to one of the at most
$n + 4c$ edges of the circuits, and has two triangles; thus these
contribute at most $2n + 8c$ triangles.
In step (3) there are two triangles added for each crossing vertex,
which totals $2c$. Thus the total is at most $3n + 14c$,
which is at most $7n^2 - 18n$ triangles, which  yields the
bound of the theorem.
$~~~\qed$

%
% Section 3
%

\section{Lower Bound Constructions}
\setcounter{equation}{0}

We present two different constructions giving quadratic lower bounds
for triangulated surfaces.

\begin{lemma}\label{genus.bound}
Let $P$ be  a closed polygonal curve
embedded in $\RR^3$ whose associated
knot type $K$ has genus $g(K)$. If $t$ is
the number of triangles in a
triangulated oriented PL surface $S$ which is embedded
in $\RR^3$ and has a subdivision of $\gamma$ as
boundary, then
\begin{equation}~\label{eq301}
t \geq 4g(K) + 1.
\end{equation}
\end{lemma}
{\bf Proof:}
Without loss of generality
we  may assume $S$ is connected, by discarding any components
having empty boundary; this only decreases $t$.
If $V, E$ and $F$ denote the number of vertices, edge and faces
in the triangulated orientable surface $S$ , then its Euler characteristic is
$$\chi(S) = V - E + F.$$
By definition of knot genus this surface is of genus $g \ge g(K)$.
Recall that the genus of a surface with boundary $S$ is the smallest
genus of a connected surface $S'$ without boundary in which it can be embedded;
In this case $S'$ is obtained by gluing in a disk attached to
the (topological) boundary $P$. 
This adds one face, and no new edges or vertices,
hence we obtain
$$\chi(S) = -1 + \chi(S')= 1 - 2g \geq  1 - 2 g(K). $$
We have $F \geq t$, and since all faces in the surface are triangles,
we obtain
$$3t = 2E - m,$$
where $m$ is the number of edges on the boundary of the surface.
Counting the number of edges on the boundary gives
$$V \geq m.$$
 From these bounds follows
$$\chi(S) \geq  1 - 2g(K) = V - E + F \geq m - (\frac{3}{2}t + \frac{m}{2})
+ t,$$
which simplifies to
$$\frac{t}{2} \geq 2g(K) - 1 + \frac{m}{2} \geq 2g(K)+ \frac{1}{2},$$
since $m \geq 3$.
$~~~\qed$

\noindent{\bf Remark.}
Define the
{\em unoriented genus} $g^*(K)$
of a knot $K$ to be the minimal value possible of
$1 - \frac{1}{2}\chi(S) $ taken over all embedded connected surfaces $S$,
orientable or not,  having
$K$ as boundary. Then $g^*(K)$ is an integer or half-integer, and
the same reasoning as above shows that 
$$ t \geq 4g^*(K) + 1$$
for the number of triangles in any triangulated PL surface
bounding a polygon $\gamma$ of knot type $K$.

\noindent{\bf Proof of Theorem~\ref{lower-oriented}:} \\
We consider the $(m, m-1)$ torus knot $K_{m, m-1}$.
This has a polygonal representation
using $n=2m$ line segments, given in
Adams et al \cite[Lemma 8.1]{AB97}.  They also show that a
polygonal realization of this knot requires at least $2m$ segments
\cite[Theorem 8.2]{AB97}.

In 1934 Seifert~\cite[Satz 4]{Se34}
showed that the $(p, q)$-torus knot $K_{p,q}$ has genus
$$g(K_{p,q}) = \frac{(p-1)(q - 1)}{2}.$$
%A generalization of this result is proved in Kauffman \cite{K83}.
Thus we have $\displaystyle g(K_{m,m-1}) = \frac{m^2 - 3m + 2}{2}.$

We apply  Lemma~\ref{genus.bound} to $K_{m, m-1}$ and obtain
$t \ge 2m^2 - 6m + 5 \ge \frac{1}{2}n^2 - 3n + 5,$
as asserted.$~~~\qed$

We next obtain a lower bound in terms of the {\em writhe}  (or {\em 
Tait number})
of a knot diagram associated to $P$ by planar projection.
The writhe of a knot diagram $K$ obtained by projecting a
knot $\gamma$ perpendicular to  a given direction, say the $z$-direction, is
obtained by assigning an orientation (direction) to the
knot diagram, and then assigning a sign of $\pm 1$ to each
crossing, with $+1$ assigned if the two directed paths of the
knot diagram at the crossing have the undercrossing oriented
by the right hand rule relative to the overcrossing, and
$-1$ if not. The writhe $w(K)$ of the oriented diagram
is the sum of these signs over all crossings.
The quantity $w(K)$ is independent of
the orientation, but depends on the direction of projection.

\begin{lemma}\label{writhe.bound}
Let $P$ be  a closed polygonal curve
embedded in $\RR^3$ that has an orthogonal  planar projection $K$
that has writhe $w(K)$.
If $t$ is the number of triangles in a complementary immersed
PL surface
in $\RR^3$ which is triangulated
and has a subdivision of $P$ as
boundary, then
\begin{equation}~\label{eq302}
t \geq |w(K)| + 1.
\end{equation}
\end{lemma}
{\bf Proof:}
The quantity $|w(K)|$ reflects
the amount of twisting between two different  longitudes
of the knot, the $z$-pushoff and the preferred  longitude.
The {\em preferred  longitude} is a longitude
on the knot defined by an embedded two-sided surface bounding
the knot $P$. The preferred  longitude is defined intrinsically as the
two primitive homology
classes $\pm [\tau]$ of a peripheral torus of the knot
that are annihilated on injecting
into $H^{1}(\RR^3 - P, \ZZ)$  (a peripheral torus
is the boundary of an
embedded regular neighborhood of the knot).
The $z$-pushoff is the curve on the peripheral torus directly above $K$
in the $z$ direction.

Any triangulated complementary immersed
surface $\sS$ having a subdivision of $P$ as
boundary necessarily defines a curve on the peripheral torus
in the class $\pm [\tau]$. The total twisting about $K$ of the boundary of a
smooth surface $\sS$ having $P$
as boundary, relative to the $z$-direction, is
given by $\pi w(K) $.
In the case of a PL surface this
total twisting can be computed by adding successive jumps in
a normal vector to $P$ pointing along the surface as one travels
along the (subdivided) curve $P$.
Since triangles are flat, twisting  occurs only at
the boundaries of two adjacent triangles, and can
be no more than $\pi$ at such a point. Furthermore,
while it is possible that a triangle meets $P$ at
as many as three points, the total twisting contributed
by any triangle at all points where it meets $P$ is
at most $\pi$, the sum of its interior angles. It follows that there must be
more than $|w(K)|$ triangles in the surface that meet
the polygon $P$. $~~~\qed$ \\

\noindent{\bf Proof of Theorem~\ref{lower-oriented2}:} \\
There exists  a family of 
polygonal curves $P_m$ for  $m \geq 1$ having
$n = 6m+3$ segments and with writhe $w(P_m) = m(m+1)$.
The knot diagram for the polygon $P_3$ is pictured
in Figure~\ref{bigwrithe}  below. The construction for
general $m$ consists of adding more parallel strands to the pattern.

\begin{figure}[hbtp]~
\centering
\includegraphics[width=.7\textwidth]{bigwrithe.eps}
\caption{Knot diagram  of polygon $P_3$.}
\label{bigwrithe}
\end{figure}

\noindent The theorem now
follows by applying the bound of Lemma~\ref{writhe.bound}, namely 
$\displaystyle t \ge \frac{n^2}{36} + \frac{3}{4}.$
$~~~\qed$ \\

Combining Lemma~\ref{writhe.bound} with the construction
of a surface in Theorem~\ref{upper-oriented}
yields a result in knot theory. It says that if
a polygon $P$ embedded in $\RR^3$ has
a large writhe in some projection direction, relative to its
number of edges $n$, then in all projection
directions it has a large number of crossings.

\begin{theorem}\label{large.writhe}
Let $P$ be a polygonal knot embedded in $\RR^3$.
If $w(K)$ is the writhe
of one projection of $P$, then the number of crossings $c$ of any
projection $K'$ of $P$ satisfies
$$c  \ge \frac{1}{16}(|w(K)| - 3n). $$
\end{theorem}
{\bf Proof:}
By Lemma~\ref{writhe.bound} one has $t \ge |w(K)| + 1$,
However if a polygon $K$ has $c$ crossings, then by the proof
of Theorem~\ref{upper-oriented} one can construct an oriented, embedded,
PL triangulated  surface having $P$ as
boundary with $t \le 3n + 14c$ triangles. Combining these
estimates gives the lemma.
$~~~\qed$

As an example, the polygons $P_m$ in $\RR^3$ 
given in the proof of Theorem~\ref{lower-oriented2}
(see  Figure~\ref{bigwrithe}) must
have crossing number
$ c \ge (m^2 - 17m - 9)/16$ in any projection.

\paragraph{Remark.} 
The  polygonal curves $P_m$ used in the proof of
Theorem~\ref{lower-oriented2}  are knotted.
(In fact they are torus knots.)
We do not know how large $|w(P)|$ can be for an
unknotted polygon with $n$ edges. 
One can easily construct representatives of the unknot having writhe
$|w(P)| > cn$, for a positive constant $c$ and $n \to \infty$, but
we do not know whether it is possible to get representations $P$ of
the unknot having $n$ crossings and writhe $|w(P)| > cn^2$
with  $n \to \infty.$ 
%If it is not possible, then one could establish
%a new type of sufficient condition for a knot diagram to be knotted,
%namely that the writhe is large enough compared to $n$.




%
% Section 4
%

\section{Higher Dimensions}
\setcounter{equation}{0}

In this section we consider polygons $P$ embedded in
$\RR^d$, for
dimensions $d \ge 4$, and construct locally flat PL surfaces having 
$P$ as boundary. Recall that a surface $\Sigma$ is 
{\em locally flat} if at
each point $\bx$ of the surface $\Sigma$ there is a neighborhood in 
$\RR^d$ homeomorphic
to $D \times I^{d - 2}$ in $\RR^d$, where $D$ is a topological $2$-disk in
the surface (or is a half $2$-disk with boundary for a boundary point $\bx$
of $\Sigma$)
and $I=[-1, 1]$ and $D \times {0}^{d-2}$ is part of $\Sigma$, 
see \cite[p. 36]{Ro76}, \cite[p. 50]{RS82}. 
For immersed surfaces we interpret local
flatness to apply to each sheet of the surface separately.

\noindent\paragraph{Proof of Theorem~\ref{four.dim}:}
We are given a closed polygon $P$ with $n$ edges embedded
in $\RR^4$, and vertices $\bv_1, ..., \bv_n$.
We can always pick a point $z \in \RR^4$
such that coning the polygon $P$ to the point $z$ will produce
a complementary immersed surface. However this surface need not
be locally flat at the cone point. To circumvent this problem,
we replace the cone point with a convex planar polygon $Q$ having $n$ vertices
and produce a  triangulated immersed
(polygonal) annulus connecting $P$ to $Q$.
Combining this with a triangulation of 
$Q$ to its centroid will yield
the desired locally flat immersed surface.

Given  a convex planar polygon $Q$ with vertices $\bw_1, ... , \bw_n$
we form the (immersed) triangulated annulus $\Sigma_1$ between $P$ and 
$Q$ with triangles $[\bv_{j}, \bv_{j+1}, \bw_{j+1}]$
and $[\bv_{j}, \bw_{j}, \bw_{j+1}]$, for
$1 \le j \le n $, using the convention that  $\bv_{n+1}:=\bv_1$
and $\bw_{n+1} :=\bw_1$. Then we triangulate $Q$ to its centroid
vertex $\bv_0$, obtaining a triangulated
disk $\Sigma_2$.  For ``general position'' $Q$ (described below)
 this  construction 
produces an immersed
 surface $\Sigma = \Sigma_1 \cup \Sigma_2$ 
consisting of  $n$ triangles from triangulating
$Q$ and $2n$ triangles in the annular part, for $3n$ triangles in all.
In general the surface $\Sigma_1$ is immersed rather than embedded,
because the triangles in it may intersect each other.

We show that $Q$ can be chosen so that $\Sigma$ is a complementary
immersed surface. The main problem is to ensure that $\Sigma_1$
intersects $P$ only in its boundary $\partial \Sigma_1$. We wish
$\Sigma_1$ to contain no line segment in any of its triangles
which intersects $P$ in two or more points. We define a ``bad set''
to avoid. Take the polygon $P$, extend its line segments to straight
lines $l_j$ in $\RR^4$, and call a point ``bad'' if it is on a line 
connecting any two points on the extended polygon. The ``bad'' set $B$
consists of a union of $n(n+1)/2$ sets $B_{ij}$,
in which $B_{ij}$ is the union of all lines
connecting a point  of  line $l_i$ to a point of line $l_j$,
with $1 \le i < j \le n$. Each $B_{ij}$ is either a hyperplane
(codimension $1$) in $\RR^4$ or is a plane (codimension $2$ flat) in $\RR^4$.
If a plane $F$ (codimension $2$ flat) is picked in ``general position''
in $\RR^4$ it will intersect $B$ in at most $n(n-1)/2$ lines and
points. In particular, such an $F$ contains 
a (two-dimensional)  open set $U$ not intersecting $B$
and disjoint from the convex hull of $P$. We
choose $Q$ to lie in this open set. Now 
$\Sigma_2$ is the convex hull of $Q$, which lies in $U$, so does
not intersect $P$. We claim 
that  $\Sigma_1$ intersects $P$ in $\partial \Sigma_1$.
Indeed any point $\bx$ in $\Sigma_1$ not on $P$ 
lies on  a line connecting a point of
$P$ to a point of $Q$, and this line contains at most one point
of $P$ because the point in $Q$ is not in the ``bad set'' $B$.
Since we already know of one point on $P$ on this line, which
is not $\bx$, the claim follows. We conclude that $\Sigma$ is
a complementary immersed surface. 


We next show that $\Sigma$ is a locally flat (immersed)
surface.  We need only verify this at the vertices of
$\Sigma$. At the vertices $\bv$ of $P$ three triangles meet,
so locally the configuration is three-dimensional, and
local flatness holds in the three-dimensional
subspace around $\bw$ determined by the edges,
(as it does for any embedded polyhedral surface in $\RR^3$)
and this extends to local flatness in $\RR^4$ by taking
a product in the remaining direction. At a
vertex $\bw$ of $Q$ five triangles meet. 
However two of these
triangles lie in the plane $F$ of the polygon $Q$, hence
for determining local flatness we may disregard the edge 
into the interior of the polygon, and treat the vertex
as having four incident triangles. Suppose the remaining
$4$ edge directions leaving $\bw$ span a four dimensional space.
Take an invertible  linear transformation $L$ that maps these vectors
to $\bx_1=(1,1, 0, 0), \bx_2=(1, -1, 0, 0), \bx_3=(-1, -1,\epsilon,0),$ 
and $\bx_4= (-1, 1, 0, \epsilon),$ in cyclic order. Because each
angle in the convex polygon is less than $\pi$, we conclude
that the interiors of all four triangles project 
onto the positive linear combinations
of consecutive vectors, e.g. the first triangle
maps into the region $\lambda_1 \bx_1 + \lambda_2\bx_2$
with $\lambda_1, \lambda_2 \ge 0$.
Now projection on the first two coordinates
in this new coordinate system extends to a local homeomorphism
$U_1 \times I^2$ in a neighborhood of the vertex, and pulling
back by $L^{-1}$ gives the required local flat structure in a
neighborhood of the vertex. If instead the four edge directions
span a three-dimensional space, then the argument used for a
vertex of $P$ applies. 
Thus $\Sigma$ is locally flat at each  vertex of $Q$.
Finally the centroid vertex added to 
the polygon $Q$ is obviously locally flat, and
we conclude that $\Sigma$ is locally flat.

Finally we note that $\Sigma$ is a topological disk, since it
is two-sided and is an annulus glued onto a disk.
$~~~\qed$


\noindent\paragraph{ Proof of Theorem~\ref{higher.dim}:}
Given the polygon $P$ in $\RR^d$, for $d \ge 5$ we cone it to a suitably
chosen point $z \in \RR^d,$ chosen so that the coning is an
embedding. It suffices to choose a ``general position'' point,
because two planes (codimension $d-2$ flats)  in $\RR^d$ gnerically have
empty intersections.
The resulting surface $\Sigma$ has $n$ triangles, and is
a topological disk.

By a standard result, see  
Rourke and Sanderson \cite[Corollary 5.7, ~Corollary 7.2]{RS82},
 this embedded surface is
locally flat. $~~~\qed$ \\



We conclude with some remarks on 
bounds for the number of triangles needed
for embedded surfaces in $\RR^4$
having a given polygon $P$ as boundary. 
First, we show
that one can
always find such a triangulated surface using at most
$24n^2$ triangles, as follows. Take a projection
of the polygon $P$ into a hyperplane $H$, resulting
in a polygon $P^{*}$ in $H$, picking a projection  direction
such that the vertical surface $\Sigma_1$ connecting $P$ to $P^{*}$
is embedded.
Theorem~\ref{upper-oriented} gives a surface $\Sigma_2$
lying entirely in $H$ which has a subdivision of $P^{**}$ of $P^{*}$
as boundary and
uses at most $7n^2$ triangles, in which the polygon $P^{**}$ has at most
$7n^2$ vertices. We obtain a
triangulated vertical surface $\Sigma_1$ connecting
$P$ to $P^{**}$ using at most $14n^2$ triangles, and
$\Sigma = \Sigma_1 \cup \Sigma_2$ is the required surface.
It  can be checked that this surface is locally flat.

Second, the immersed
surface constructed in Theorem~~\ref{four.dim} can
be converted to an embedded surface of higher genus
by cut-and paste, but we show that such a surface will contain
$\Omega(n^2)$ triangles in some cases. 
Recall that the {\em $4$-ball genus} of
a knot embedded in
a hyperplane in $\RR^4$ is the smallest genus
of any spanning surface of it
that lies strictly in a half-space of $\RR^4$ on one
side of this hyperplane.
If we start with
a polygon $P$ in $\RR^4$ that lies in a hyperplane, the
construction of Theorem~\ref{four.dim} will (in general) produce
an immersed surface lying in a half-space on one side of the
hyperplane, and a cut-and-paste construction will preserve
this property. (Note that cut-and-paste in $4$-dimensions
to replace two triangles intersecting in an interior point
with a nonintersecting set may result in eight triangles.)
As noted earlier, the  $(2n, 2n-1)$ torus knot has a polygonal
representation $P_n$ in a hyperplane using $4n$ line segments
(Adams et al \cite[Lemma 8.1]{AB97})
while a result of Shibuya~\cite{Sh86} implies
that its 4-ball genus is
at least $2n(2n-1)/8$. Applying
Lemma~\ref{genus.bound}, we conclude that the number of
triangles needed in an embedded orientable PL surface
of this type spanning
$P_n$ must grow quadratically
in $n$. This can be taken as (weak) evidence in support of
the possibility that for embedded surfaces in $\RR^4$
the best combinatorial isoperimetric bound may be
$O(n^2)$. \\ 






%\newpage
\begin{thebibliography}{99}

\bibitem{AB97}
C. Adams, B. M. Brennan, D. L. Greilsheimer and A. K. Woo,
Stick numbers and composition of knots and links,
J. Knot Theory Ramifications {\bf 6} (1997), 149--161.

\bibitem{AT77}
F. J. Almgren and W. P. Thurston,
Examples of unknotted curves that only bound surfaces of
high genus within their convex hulls,
{\em Ann. Math.} {\bf 105} (1977), 527--538.

%\bibitem{AE87}
%D. Avis and H. ElGindy,
%Triangulating point sets in space,
%{\em Disc. \& Comp. Geom.} {\bf 2} (1987), 99--111.

\bibitem{BR33}
E. F. Beckenbach and T. Rado,
Subharmonic functions and surfaces of negative curvature,
{\em Trans. Amer. Math. Soc.} {\bf 35} (1933), 662--682.


\bibitem{Bla30}
W. Blaschke,
{\em Vorlesungen \"{u}ber Differentialgeometrie I},
Third Ed., Springer-Verlag: Berlin 1930.

\bibitem{BZ88}
Yu. D. Burago and V. A. Zalgaller,
{\em Geometric Inequalities},
Springer-Verlag: Berlin 1988.



%\bibitem{Ch84}
%B. Chazelle,
%Convex partitions of polyhedra: a lower bound
%and worst case optimal algorithm,
%SIAM J. Comput. {\bf 13} (1984), 488--507.


\bibitem{FLS99}
E. Furstenber, Jie Li and J. Schneider,
Stick knots,
Chaos, Solitons and Fractals {\bf 9} (1998), 561--568.

\bibitem{HL}
J. Hass and J. C. Lagarias,
The number of Reidemeister moves needed for unknotting,
{\em J. Amer. Math. Soc.} 14 (2001), 399-428.

\bibitem{HLP}
J. Hass, J. C. Lagarias and N. Pippenger,
The computational complexity of knot and link problems,
{\em J. ACM} 46 (1999), no. 2, 185--211.

\bibitem{HLT}
J. Hass, J. C. Lagarias and W. P. Thurston,
Area inequalities for embedded disks bounding unknotted curves,
in preparation.

\bibitem{HST}
J. Hass, J. S.  Snoeyink and W. P. Thurston,
The  size of spanning disks for polygonal knots,
Discrete \& Computational Geometry, submitted.
eprint: {\tt arXiv math.GT/9906197}.

\bibitem{H80}
J. H. Hubbard,
On the convex hull genus of space curves,
Topology {\bf 19} (1980), 203--208.

\bibitem{Os76}
R. Osserman,
The isoperimetric inequality,
Bull. Amer. Math. Soc. {\bf 84} (1978), 1182--1238.

\bibitem{Ro76}
D. Rolfsen,
{\em Knots and Links,}
Math. Lecture Series No. 7, Publish or Perish: Berkeley, Cal. 1976.

\bibitem{RS82}
C. P. Rourke and B. J. Sanderson,
{\em Introduction to Piecewise-Linear Topology,} 
Springer-Verlag: New York-Heidelberg 1982.



\bibitem{Se34}
H. Seifert,
\"{U}ber das Geschlecht von Knoten,
Math. Ann. {\bf 110} (1934), 571--592.

\bibitem{Sh86}
T. Shibuya,
A lower bound of $4$-genus for torus knots,
Mem. Oaska Inst. Tech. Ser. A {\bf 31} (1986), 11--17.

\bibitem{Su97}
S. Suri,
 Polygons, 
in: {\em Handbook of Computational Geometry},
(J. E. Goodman and J. O'Rourke, Eds.), Chapter 23,
CRC Press, Boca Raton, FL 1997.
\end{thebibliography}

{\tt
\begin{tabular}{ll}
email: & hass@math.ucdavis.edu \\
&  jcl@research.att.com
\end{tabular}
  }

\end{document}



math0202179.extracted_bib
\begin{thebibliography}{99}

\bibitem{AB97}
C. Adams, B. M. Brennan, D. L. Greilsheimer and A. K. Woo,
Stick numbers and composition of knots and links,
J. Knot Theory Ramifications {\bf 6} (1997), 149--161.

\bibitem{AT77}
F. J. Almgren and W. P. Thurston,
Examples of unknotted curves that only bound surfaces of
high genus within their convex hulls,
{\em Ann. Math.} {\bf 105} (1977), 527--538.

%\bibitem{AE87}
%D. Avis and H. ElGindy,
%Triangulating point sets in space,
%{\em Disc. \& Comp. Geom.} {\bf 2} (1987), 99--111.

\bibitem{BR33}
E. F. Beckenbach and T. Rado,
Subharmonic functions and surfaces of negative curvature,
{\em Trans. Amer. Math. Soc.} {\bf 35} (1933), 662--682.


\bibitem{Bla30}
W. Blaschke,
{\em Vorlesungen \"{u}ber Differentialgeometrie I},
Third Ed., Springer-Verlag: Berlin 1930.

\bibitem{BZ88}
Yu. D. Burago and V. A. Zalgaller,
{\em Geometric Inequalities},
Springer-Verlag: Berlin 1988.



%\bibitem{Ch84}
%B. Chazelle,
%Convex partitions of polyhedra: a lower bound
%and worst case optimal algorithm,
%SIAM J. Comput. {\bf 13} (1984), 488--507.


\bibitem{FLS99}
E. Furstenber, Jie Li and J. Schneider,
Stick knots,
Chaos, Solitons and Fractals {\bf 9} (1998), 561--568.

\bibitem{HL}
J. Hass and J. C. Lagarias,
The number of Reidemeister moves needed for unknotting,
{\em J. Amer. Math. Soc.} 14 (2001), 399-428.

\bibitem{HLP}
J. Hass, J. C. Lagarias and N. Pippenger,
The computational complexity of knot and link problems,
{\em J. ACM} 46 (1999), no. 2, 185--211.

\bibitem{HLT}
J. Hass, J. C. Lagarias and W. P. Thurston,
Area inequalities for embedded disks bounding unknotted curves,
in preparation.

\bibitem{HST}
J. Hass, J. S.  Snoeyink and W. P. Thurston,
The  size of spanning disks for polygonal knots,
Discrete \& Computational Geometry, submitted.
eprint: {\tt arXiv math.GT/9906197}.

\bibitem{H80}
J. H. Hubbard,
On the convex hull genus of space curves,
Topology {\bf 19} (1980), 203--208.

\bibitem{Os76}
R. Osserman,
The isoperimetric inequality,
Bull. Amer. Math. Soc. {\bf 84} (1978), 1182--1238.

\bibitem{Ro76}
D. Rolfsen,
{\em Knots and Links,}
Math. Lecture Series No. 7, Publish or Perish: Berkeley, Cal. 1976.

\bibitem{RS82}
C. P. Rourke and B. J. Sanderson,
{\em Introduction to Piecewise-Linear Topology,} 
Springer-Verlag: New York-Heidelberg 1982.



\bibitem{Se34}
H. Seifert,
\"{U}ber das Geschlecht von Knoten,
Math. Ann. {\bf 110} (1934), 571--592.

\bibitem{Sh86}
T. Shibuya,
A lower bound of $4$-genus for torus knots,
Mem. Oaska Inst. Tech. Ser. A {\bf 31} (1986), 11--17.

\bibitem{Su97}
S. Suri,
 Polygons, 
in: {\em Handbook of Computational Geometry},
(J. E. Goodman and J. O'Rourke, Eds.), Chapter 23,
CRC Press, Boca Raton, FL 1997.
\end{thebibliography}