The size of spanning disks for unknotted polygonal curves: exponential lower bound versus $C^{n^2}$ upper bound

For an unknotted closed polygonal curve $K$ in $\mathbb{R}^3$ with $n$ edges, let $t(K)$ be the minimal number of triangular faces in a piecewise-linear (PL) embedded triangulated disk in $\mathbb{R}^3$ whose boundary is $K$. Hass, Snoeyink and Thurston (Discrete Comput. Geom. 29(1):1-17, 2002) constructed explicit unknotted polygons $K_n$ with fewer than $10n+9$ edges such that every PL spanning disk contains at least $2^{n-1}$ triangles, while normal-surface arguments of Hass, Lagarias and Pippenger (1999) and Hass, Lagarias and Thurston (2004) give a general upper bound of only $C^{n^2}$ triangles. The exponent $n^2$ comes from the $O(n^2)$ tetrahedra needed to place an arbitrary $n$-edge polygon in the 1-skeleton of a triangulated 3-ball, not from any known lower-bound phenomenon. Whether the gap can be closed — in particular whether a single-exponential upper bound $C^n$ holds for all unknotted polygons, or at least for polygons whose vertices are in general position, as the source paper suggests is plausible — has remained open since 2002. The problem asks to determine the correct asymptotic class of the worst-case minimal spanning-disk triangle count: improve the upper bound to $C^n$, or exhibit unknotted polygons requiring super-exponentially many triangles.

Background

A closed polygonal curve in $\mathbb{R}^3$ is a simple closed curve made of finitely many straight segments; it is unknotted if it bounds an embedded disk, equivalently if it can be continuously deformed without self-intersection onto a planar circle. A PL spanning disk of such a curve $K$ is a triangulated disk, embedded in $\mathbb{R}^3$ with flat triangular faces, whose boundary is $K$ (the boundary edges of the disk may subdivide the edges of $K$). The question studied by Hass, Snoeyink and Thurston (HST) is: measured by the number of edges $n$ of $K$, how many triangles must such a disk have in the worst case?

The question originates in computational topology. Haken's 1961 algorithm decides unknottedness by searching, in the language of normal surface theory, for a spanning disk: given a triangulated 3-manifold with $t$ tetrahedra, essential surfaces can be found among `fundamental' normal surfaces, which are cut into standard triangular and quadrilateral pieces and whose piece counts are at most $2^{O(t)}$ (the integer coordinates of fundamental solutions are exponentially bounded). Hass, Lagarias and Pippenger (J. ACM 1999) used this to prove that unknot recognition is in NP, the certificate being a spanning disk. To apply the machinery to a polygon, one first embeds the curve in the 1-skeleton (the union of vertices and edges) of a triangulated 3-ball, and an arbitrary $n$-edge polygon forces $t = O(n^2)$ tetrahedra: Avis and El Gindy showed that some $n$-point sets in $\mathbb{R}^3$ require $\Omega(n^2)$ tetrahedra to triangulate, although point sets in general position (no four points coplanar, no three collinear) admit triangulations with only $O(n)$ simplices. Hass, Lagarias and Thurston (J. Differential Geom. 2004) converted the elementary-move machinery of Hass and Lagarias into the bound: if an unknotted $K$ lies in the 1-skeleton of a $t$-tetrahedron triangulated 3-manifold, then $K$ has a spanning disk with at most $C^t$ triangles. This yields the general upper bound $C^{n^2}$, and no better bound is known.

The matching construction of HST shows the answer is at least single-exponential. Their curves $K_n$ are obtained by closing the 4-strand braid $(\sigma_1\sigma_2^{-1})^n(\sigma_2\sigma_1^{-1})^n$, where $\sigma_i$ are the standard Artin generators of the braid group on four strands (whose elements are isotopy classes of four disjoint strands running monotonically between two parallel planes; the generator $\sigma_i$ exchanges the $i$-th and $(i+1)$-st strands by a half-twist). Sliding a cross-section plane along the braid realizes the monodromy $\varphi$ of $\sigma_1\sigma_2^{-1}$ on the four-punctured plane (the return map recording how the plane has moved after one pass along the braid), a pseudo-Anosov homeomorphism (one that stretches along a pair of transverse measured foliations by a dilatation $\lambda>1$; here $\lambda$ is the square of the golden ratio). Any spanning disk is, up to a controlled number of saddle singularities, transverse to the levels of the braid, so one of its cross-sections is isotopic to an iterate $\varphi^k$ of fixed arcs, whose intersections with a fixed line grow like $\lambda^k$. Since a flat triangle meets a line at most once, every PL spanning disk of $K_n$ has at least $2^{n-1}$ triangles — in fact at least a constant times $\phi^{2n}$, where $\phi$ is the golden ratio — while $K_n$ has fewer than $10n+9$ edges (at most $6n$ in an efficient embedding).

Several contrasts locate the difficulty. If the disk is allowed to self-intersect, $O(n)$ triangles suffice for the HST curves; if embedded orientable spanning surfaces of arbitrary genus (Seifert surfaces, i.e. surfaces allowed to have handles) are allowed, Hass and Lagarias showed every $n$-edge polygon has one with at most $7n^2$ triangles and knotted polygons sometimes require at least $n^2/2 - O(n)$, so $\Theta(n^2)$ is the right answer there. The exponential phenomenon is thus specific to embedded disks of unknots. For diagrams given with $c$ crossings, Hass, Lagarias and Pippenger build an exterior triangulation with only $t = O(c)$ tetrahedra, so a spanning disk of the diagram-realized curve has $2^{O(c)}$ triangles — single-exponential in the diagram size, and essentially tight by the HST family. The polygonal model is harder for two reasons: an $n$-edge polygon need not admit any projection with $O(n)$ crossings, and the disk must follow the given geometry exactly, since converting a disk for an isotopic copy of the curve back to the exact boundary is precisely where the blowup occurs.

HST explicitly note that the exponent $n^2$ in the upper bound `comes from the requirement that the polygon be embedded in the 1-skeleton of a triangulated 3-manifold', that this requirement cannot always be improved for point sets (Avis and El Gindy), and state: "It seems plausible that one could obtain an improved upper bound of $C^n$ triangles for a PL spanning disk of a polygon whose vertices are in general position." Both the general gap and the general-position variant remain open.

Problem Statement

Let $T(n)$ denote the maximum, over all unknotted closed polygonal curves $K \subset \mathbb{R}^3$ with at most $n$ edges, of the minimal number of triangular 2-faces in a PL embedded triangulated disk $D \subset \mathbb{R}^3$ whose boundary is $K$ (as a point set; the boundary edges of $D$ may subdivide the edges of $K$). It is known that $c_1^n \le T(n) \le c_2^{n^2}$ for constants $c_1, c_2 > 1$ independent of $n$: the lower bound is the Hass-Snoeyink-Thurston family $K_n$ (fewer than $10n+9$ edges, every spanning disk has at least $2^{n-1}$ triangles), and the upper bound follows from normal-surface theory once the polygon is placed in the 1-skeleton of a triangulated 3-ball with $O(n^2)$ tetrahedra (Hass-Lagarias-Thurston). Determine the correct asymptotic class of $T(n)$. Concretely, the following three directions bear on the question:

(1) Single-exponential upper bound: prove that there is a constant $C$ such that every unknotted polygonal curve with at most $n$ edges admits an embedded PL spanning disk with at most $C^n$ triangles (which, combined with the known lower bound, would give $T(n) = 2^{\Theta(n)}$).

(2) Super-exponential lower bound: construct an explicit family of unknotted polygonal curves with $O(n)$ edges for which every embedded PL spanning disk requires $2^{\omega(n)}$ triangles (for example at least $2^{n^{1+\varepsilon}}$; a family requiring at least $c^{n^2}$ would show the known upper bound is tight), demonstrating that the quadratic exponent in the current upper bound is not merely an artifact of the 1-skeleton embedding step.

(3) General-position upper bound: does the bound of (1) hold under the hypothesis that the polygon's vertex set is in general position (no four vertices coplanar and no three collinear)? This is the regime in which the vertex set admits a triangulation with $O(n)$ simplices (Avis-El Gindy), so the $n^2$ in the current upper bound comes from hosting the curve's edges, not just its vertices, and whether that obstruction can be removed under general position is unresolved.

References

1. Joel Hass, Jack Snoeyink, William P. Thurston, 'The Size of Spanning Disks for Polygonal Curves', Discrete & Computational Geometry 29(1):1-17, 2002 (issue dated December 2002). DOI: 10.1007/s00454-002-2707-6, https://doi.org/10.1007/s00454-002-2707-6; arXiv: math/9906197, https://arxiv.org/abs/math/9906197
2. Joel Hass, Jeffrey C. Lagarias, William P. Thurston, 'Area Inequalities for Embedded Disks Spanning Unknotted Curves', Journal of Differential Geometry 68:1-30, 2004. DOI: 10.4310/jdg/1102536708, https://doi.org/10.4310/jdg/1102536708; arXiv: math/0306313, https://arxiv.org/abs/math/0306313
3. Joel Hass, Jeffrey C. Lagarias, 'The Minimal Number of Triangles Needed to Span a Polygon Embedded in R^d' (the arXiv preprint is titled 'The Number of Triangles Needed to Span a Polygon Embedded in R^d'), in: Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Algorithms and Combinatorics vol. 25, Springer, 2003, pp. 509-526. DOI: 10.1007/978-3-642-55566-4_23, https://doi.org/10.1007/978-3-642-55566-4_23; arXiv: math/0211364, https://arxiv.org/abs/math/0211364
4. Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger, 'The Computational Complexity of Knot and Link Problems', Journal of the ACM 46(2):185-211, 1999. DOI: 10.1145/301970.301971, https://doi.org/10.1145/301970.301971; arXiv: math/9807016, https://arxiv.org/abs/math/9807016
5. Joel Hass, Jeffrey C. Lagarias, 'The Number of Reidemeister Moves Needed for Unknotting', Journal of the American Mathematical Society 14(2):399-428, 2001. DOI: 10.1090/s0894-0347-01-00358-7, https://doi.org/10.1090/s0894-0347-01-00358-7; arXiv: math/9807012, https://arxiv.org/abs/math/9807012
6. David Avis, Hossam ElGindy, 'Triangulating point sets in space', Discrete & Computational Geometry 2(2):99-111, 1987. DOI: 10.1007/BF02187874, https://doi.org/10.1007/BF02187874
7. Jack Snoeyink, 'A trivial knot whose spanning disks have exponential size', Proceedings of the 6th Annual ACM Symposium on Computational Geometry, 1990, pp. 139-147. DOI: 10.1145/98524.98555, https://doi.org/10.1145/98524.98555
8. Marc Lackenby, 'Elementary knot theory', 2016. arXiv: 1604.03778, https://arxiv.org/abs/1604.03778
9. Marc Lackenby, 'Algorithms in 3-manifold theory', 2020. arXiv: 2002.02179, https://arxiv.org/abs/2002.02179
10. Marc Lackenby, 'The efficient certification of knottedness and Thurston norm', Advances in Mathematics 387:107796, 2021. DOI: 10.1016/j.aim.2021.107796, https://doi.org/10.1016/j.aim.2021.107796; arXiv: 1604.00290, https://arxiv.org/abs/1604.00290
11. Marc Lackenby, 'A polynomial upper bound on Reidemeister moves', Annals of Mathematics 182(2):491-564, 2015. DOI: 10.4007/annals.2015.182.2.3, https://doi.org/10.4007/annals.2015.182.2.3; arXiv: 1302.0180, https://arxiv.org/abs/1302.0180
12. Marc Lackenby, 'A polynomial upper bound on Reidemeister moves for each link type', 2026. arXiv: 2602.09923, https://arxiv.org/abs/2602.09923
13. Benjamin A. Burton, Hsien-Chih Chang, Maarten Loffler, Arnaud de Mesmay, Clement Maria, Saul Schleimer, Eric Sedgwick, Jonathan Spreer, 'Hard Diagrams of the Unknot', Experimental Mathematics 33(3):482-500, 2024 (published online February 2023). DOI: 10.1080/10586458.2022.2161676, https://doi.org/10.1080/10586458.2022.2161676; arXiv: 2104.14076, https://arxiv.org/abs/2104.14076
14. Marc Lackenby, 'Incompressible surfaces, hierarchies and unknot recognition', 2026. arXiv: 2607.23350, https://arxiv.org/abs/2607.23350
15. Wolfgang Haken, 'Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten', Acta Mathematica 105:245-375, 1961. DOI: 10.1007/BF02559591, https://doi.org/10.1007/BF02559591
16. Bernard Chazelle, 'Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm', SIAM Journal on Computing 13(3):488-507, 1984. DOI: 10.1137/0213031, https://doi.org/10.1137/0213031