The minimal number of triangles needed to span a polygon embedded in \(\mathbb R^d\). (English) Zbl 1103.52013

Hass, Joel; Lagarias, Jeffrey C.

Aronov, Boris (ed.) et al., Discrete and computational geometry. The Goodman-Pollack Festschrift. Berlin: Springer (ISBN 3-540-00371-1/hbk). Algorithms Comb. 25, 509-526 (2003).

Authors’ abstract: Given a closed polygon \(P\) having \(n\) edges, embedded in \(\mathbb R^d\), we give upper and lower bounds for the minimal number of triangles \(t\) needed to form a triangulated PL surface embedded in \(\mathbb R^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 \(\mathbb R^d\) and whose interior is disjoint from \(P\). The most interesting case is dimension \(3\), where the polygon may be knotted.
We use the Seifert surface construction to show that for any polygon embedded in \(\mathbb R^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. We also exhibit families of polygons in \(\mathbb R^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 \geq 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. These results can be viewed as providing qualitative discrete analogues of the isoperimetric inequality for piecewise linear (PL) manifolds. In dimension \(3\) they imply that the (asymptotic) discrete isoperimetric constant lies between \(1/2\) and \(7\).
For the entire collection see [Zbl 1014.00040].

Reviewer: Frank Lutz (Berlin)

MSC:

52B70	Polyhedral manifolds
57Q35	Embeddings and immersions in PL-topology
57Q15	Triangulating manifolds
52B05	Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
57M25	Knots and links in the \(3\)-sphere (MSC2010)
52B60	Isoperimetric problems for polytopes
53A10	Minimal surfaces in differential geometry, surfaces with prescribed mean curvature

Keywords:

polygonal curve; spanning PL surface; knot genus; isoperimetric inequality; Plateau’s problem