Date: Mon, 6 Mar 1995 16:45 PST
From: [Permission pending]
Subject: triangulations
To: rusin@math.niu.edu

Dave,
[deletia - djr]

So, are minimal #'s of points to triangulate various surfaces -- like the
2-torus -- known, independent of whether the triangulations are embeddable
in R^3?

[sig deleted]

==============================================================================
Date: Tue, 7 Mar 95 01:29:26 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re:  triangulations

I don't really know what limits on the polyhedral embeddings are known.

The spaces are very easy to triangulate, in the sense of CW complexes.
If you look at the homology of the  n-holed torus, you get Z, Z^2n, Z in
dimensions  0, 1, and  2 respectively. Since homology can be computed from
any cellular decomposition of the space, there must be at least one vertex,
2n edges, and 1 2-cell. This is in fact the usual presentation of the n-holed
torus: take the 2-cell to be a 4n-sided polygon, and identify edges 4i with
4i+2 and 4i+1 with 4i+3, reversing orientations each time.These identifications
yield one vertex, 2n edges, and the one 2-cell. If you want a cellular decomposition
in which the boundary of each 2-cell maps just to 3 one-cells (as with
triangles) you can decompose the 4n-gon into 4n-2 triangles. By Euler's 
formula, 4n-2 is the minimum number of triangles if you stick to  1  vertex.

This is NOT a triangulation in the sense that each closed 2-cell is HOMEMORPHIC
to a triangle; for example, this method collapses the three vertices of each
triangle to a point. If you want something more polyhedron-like, you might 
want to assume that every edge connects two distinct vertices, and that
between any two vertices there is at most one edge. This gives the lower
bound (7+sqrt(1+48n))/2 on the number of vertices, as I posted, but I think
a lower bound linear in  n  is possible: the fundamental group of a (connected)
graph of  E  edges and  V  vertices is the free group on  E-V+1 generators;
each addition of a _triangle_ will introduce a relation of length at most  3,
but the final fundamental group is 2n-generated witha single relation which
is of length 4n in the generators. So I think you need O(n) vertices. I haven't
pinned this argument down yet, though. So I'm not sure if this number of vertices
is necessary, but certainly a number linear in  n  is sufficient: just use the 
polygonal model above, trisecting each of the 2n edges with 2 new points 
between the one common point, and add a vertex facing each edge of the
polygon. Connect each of these interior vertices to 3 consecutive edge
ones, and then subdivide the remaining part of the polygon with edges joining
only internal vertices.


Given a decomposition of the surface into triangles meeting the above
conditions, the description is purely combinatorial: you can describe the
space by specifying that there are  V  distinct vertices, E edges joining
certain pairs, and  F faces joining certain triples. Once this is done, 
the surface may be polyhedrally embedded in  R^V, simply by putting each
vertex on a separate basis element of this vector space, and then taking
the union of the appropriate convex hulls. So for example I can divide an
octagon into  24 triangles sort of like above and observe that now there are 
(1 central)+(1 corner)+(8/4 x 2 edge) = 10 vertices; each triangle and
each of the 36 edges is uniquely specified as the span of some of these
vertices. Thus I have an embedding of the 2-holed torus in R^10 using
10 vertices. I have not yet found (or disporved the existence of) a
combinatorial decomposition of the 2-holed torus with  9 vertices. If one
exists, then the space embeds polyhedrally in R^9.

As for finding an embedding into R^3, note that by the combinatorial
nature of the decomposition, it suffices to find a mapping of each of the
vertices into  R^3 and extend by linearity. Since the vertices are a basis
for  R^V, this makes the job equivalent to finding a projection 
R^V --> R^3  which is one-to-one. I don't know how to decide whether or not
one exists. 

So the question of whether a polyhedral embedding with a certain number of
vertices exists in  R^3  has a number of different obstructions. I don't
know what kind of progress is known. I got no responses to my post other
than your followup.

Incidentally, I think the Gauss-Bonnet theorem may have an impact. At the
very least, since there is a global constraint on curvature, there will
be some balancing of the acute and obtuse dihedral angles. This kind of global
invariant may be what inhibits projections from  R^V  to  R^3.

If you want high-powered reading on this stuff look up triangularizations
of manifolds, including the work of  Bing. This fancy name is "PL topology"
(piecewise linear) and there are some deep facts wellknown by some but not
by me.

dave