3 added 209 characters in body

Does every polyhedron in $\mathbb{R}^3$ with $n$ triangular facets have a topological triangulation with complexity $O(n)$?

Suppose $P$ is a non-convex polyhedron in $\mathbb{R}^3$ with $n$ triangular facets, possibly with positive genus. A topological triangulation of $P$ is a simplicial complex whose underlying space is the closure of the interior of $P$, such that every facet of $P$ is a cell in the complex. These boundary facets are true geometric triangles, but interior simplices may be arbitrarily bent and twisted. In the more standard geometric triangulations, every simplex is the convex hull of its vertices.

Results of Chazelle and Shouraboura imply that every polyhedron has a geometric triangulation with complexity $O(n^2)$. Moreover, a classical construction of Chazelle implies that the $O(n^2)$ bound is is optimal in the worst case, even when the genus is zero.

But we can get tighter bounds for topological triangulations, at least for genus-zero polyhedra. If $P$ has genus zero, Steinitz's theorem implies that there is a convex polyhedron $Q$ that is combinatorially equivalent to $P$. Alexander's extension of the Schönflies theorem implies that the interiors of $P$ and $Q$ are both homeomorphic to open balls. Thus, applying a suitable homeomorphism to a minimal geometric triangulation of $Q$ gives us a topological triangulation of $P$ with complexity $O(n)$. (Alternatively, we can triangulate $P$ by joining an arbitrary interior point to every facet.)

What makes the question tricky for higher-genus polyhedra is the possibility of knottedness; the topology of the interior of $P$ is not determined by its genus. Intuitively, the question is how knotted the interior of a polyhedron can be, as a function of the number of facets.

The following question may be equivalent: Let $K$ be a closed polygonal chain (or "stick knot") in $S^3$ with $n$ edges. Is there a topological triangulation of $S^3$ with complexity $O(n)$ that includes $K$ in its 1-skeleton? Again, if we insist on geometric triangulations, $\Theta(n^2)$ tetrahedra are always sufficient and sometimes necessary, even if $K$ is unknotted.

Added for bounty (Apr 13): Partial results, subquadratic upper bounds, or references that imply this problem is open (or the crossing-number problem in my comment on the first answer) would be welcome.

2 deleted 128 characters in body

Does every polyhedron in $\mathbb{R}^3$ with $n$ triangular facets have a topological triangulation with complexity $O(n)$?

Suppose $P$ is a non-convex polyhedron in $\mathbb{R}^3$ with $n$ triangular facets, possibly with positive genus. A topological triangulation of $P$ is a simplicial complex whose underlying space is the closure of the interior of $P$, such that every facet of $P$ is a cell in the complex. These boundary facets are true geometric triangles, but interior simplices may be arbitrarily bent and twisted. In the more standard geometric triangulations, every simplex is the convex hull of its vertices.

Results of Chazelle and Shouraboura imply that every polyhedron has a geometric triangulation with complexity $O(n^2)$. Moreover, a classical construction of Chazelle implies that the $O(n^2)$ bound is is optimal in the worst case, even when the genus is zero.

But we can get tighter bounds for topological triangulations, at least for genus-zero polyhedra. If $P$ has genus zero, Steinitz's theorem implies that there is a convex polyhedron $Q$ that is combinatorially equivalent to $P$. Alexander's extension of the Schönflies theorem implies that the interiors of $P$ and $Q$ are both homeomorphic to open balls. Thus, applying a suitable homeomorphism to a minimal geometric triangulation of $Q$ gives us a topological triangulation of $P$ with complexity $O(n)$.

Chazelle and Shouraboura's results imply that any polyhedron (Alternatively, we can triangulate $P$ is homeomorphic to a polyhedron $Q$ that has a triangulation with complexity $O(n)$, but the by joining an arbitrary interior of $P$ may not be homeomorphic point to the interior of $Q$. every facet.)

What makes the question tricky for higher-genus polyhedra is the possibility of knottedness; the topology of the interior of $P$ is not determined by its genus. Intuitively, the question is how knotted the interior of a polyhedron can be, as a function of the number of facets.

The following question may be equivalent: Let $K$ be a closed polygonal chain (or "stick knot") in $S^3$ with $n$ edges. Is there a topological triangulation of $S^3$ with complexity $O(n)$ that includes $K$ in its 1-skeleton? Again, if we insist on geometric triangulations, $\Theta(n^2)$ tetrahedra are always sufficient and sometimes necessary, even if $K$ is unknotted.

1

# Efficient topological triangulations of non-convex polyhedra

Does every polyhedron in $\mathbb{R}^3$ with $n$ triangular facets have a topological triangulation with complexity $O(n)$?

Suppose $P$ is a non-convex polyhedron in $\mathbb{R}^3$ with $n$ triangular facets, possibly with positive genus. A topological triangulation of $P$ is a simplicial complex whose underlying space is the closure of the interior of $P$, such that every facet of $P$ is a cell in the complex. These boundary facets are true geometric triangles, but interior simplices may be arbitrarily bent and twisted. In the more standard geometric triangulations, every simplex is the convex hull of its vertices.

Results of Chazelle and Shouraboura imply that every polyhedron has a geometric triangulation with complexity $O(n^2)$. Moreover, a classical construction of Chazelle implies that the $O(n^2)$ bound is is optimal in the worst case, even when the genus is zero.

But we can get tighter bounds for topological triangulations, at least for genus-zero polyhedra. If $P$ has genus zero, Steinitz's theorem implies that there is a convex polyhedron $Q$ that is combinatorially equivalent to $P$. Alexander's extension of the Schönflies theorem implies that the interiors of $P$ and $Q$ are both homeomorphic to open balls. Thus, applying a suitable homeomorphism to a minimal geometric triangulation of $Q$ gives us a topological triangulation of $P$ with complexity $O(n)$.

Chazelle and Shouraboura's results imply that any polyhedron $P$ is homeomorphic to a polyhedron $Q$ that has a triangulation with complexity $O(n)$, but the interior of $P$ may not be homeomorphic to the interior of $Q$. What makes the question tricky for higher-genus polyhedra is the possibility of knottedness; the topology of the interior of $P$ is not determined by its genus. Intuitively, the question is how knotted the interior of a polyhedron can be, as a function of the number of facets.

The following question may be equivalent: Let $K$ be a closed polygonal chain (or "stick knot") in $S^3$ with $n$ edges. Is there a topological triangulation of $S^3$ with complexity $O(n)$ that includes $K$ in its 1-skeleton? Again, if we insist on geometric triangulations, $\Theta(n^2)$ tetrahedra are always sufficient and sometimes necessary, even if $K$ is unknotted.