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