**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.