The Number of Triangles Needed to Span a Polygon Embedded in R^d

2002/11/22 by Joel Hass, Jeffrey C. Lagarias
Mathematics · #math.GT #math.DG #math.MG #msc:53A10 #msc:52B60 #msc:57Q15

paper · pdf

published as pp. 509--526 in: Discrete and Computational Geometry: The Goodman-Pollack Festscrift, (B. Aronov, S. Basu, J. Pach and M. Sharir, Eds.), Springer-Verlag, New York 2003. · 16 pages, 4 figures. This paper is a retitled, revised version of math.GT/0202179

arxiv created 2002/11/22 · arxiv updated 2009/11/30

Abstract

Given a closed polygon P having n edges, embedded in R^d, we give upper and lower bounds for the minimal number of triangles t needed to form a triangulated PL surface in R^d having P as its geometric boundary. The most interesting case is dimension 3, where the polygon may be knotted. We use the Seifert suface construction to show there always exists an embedded surface requiring at most 7n² triangles. We complement this result by showing there are polygons in R³ for which any embedded surface requires at least 1/2n² - O(n) triangles. In dimension 2 only n-2 triangles are needed, and in dimensions 5 or more there exists an embedded surface requiring at most n triangles. In dimension 4 we obtain a partial answer, with an O(n²) upper bound for embedded surfaces, and a construction of an immersed disk requiring at most 3n triangles. These results can be interpreted as giving qualitiative discrete analogues of the isoperimetric inequality for piecewise linear manifolds.

Related

• Affine isoperimetric inequalities for piecewise linear surfaces
• The size of spanning disks for polygonal curves
• Non-compact Riemann surfaces are equilaterally triangulable
• The extremal number of surfaces
• Approximating Surfaces in R³ by Meshes with Guaranteed Regularity