**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](http://www.cs.princeton.edu/~chazelle/pubs/BoundsSizeTetrahedral.pdf) imply that every polyhedron has a geometric triangulation with complexity $O(n^2)$. Moreover, a classical construction of [Chazelle](http://www.cs.princeton.edu/~chazelle/pubs/ConvexPartitionPolyhedra.pdf) 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](http://en.wikipedia.org/wiki/Steinitz%27s_theorem) implies that there is a *convex* polyhedron $Q$ that is combinatorially equivalent to $P$. [Alexander's extension of the Schönflies theorem](http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1085499/) 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.



Efficient topological triangulations of non-convex polyhedra
I've been thinking about the main question in the original post on and off for a few days. All of my efforts have been in the direction of finding enough examples to prove a super-linear lower bound, following Misha's suggestion to use hyperbolic volume. This hasn't worked yet - the problem appears to be tricky! In any case, here is the most appealing of the constructions. 


**Stick braids**


Let $x, y, z$ be the usual coordinates on $\mathbb{R}^3$. Let $D$ be the unit disk in the plane $z = 0$ and let $E$ be the unit disk in the plane $z = 1$. Suppose that $\{a\_i\}\_1^n \subset D$ is a collection of points. Let $b\_i$ be the point in $E$ with the same $x$ and $y$ coordinates as $a\_i$. Suppose that $\sigma \in \Sigma\_n$ is a permutation. Let $B = B(a, \sigma)$ be the collection of line segments where the $i$'th segment has endpoints $a\_i$ and $b\_{\sigma(i)}$. If the segments are pairwise disjoint then we call $B$ a *stick braid*.


It follows that the braid closure of $B$ is a link with stick number at most $5n$. As a concrete example, the $(p,q)$-torus knot can be obtained by placing the points $a\_i$ at the $p$'th roots of unity, taking $\sigma(i) = i + q$, modulo $p$, and taking a braid closure. 


**Hyperbolic volume**


Now we must use the Euclidean geometry of the braid $B$ to draw conclusions about the hyperbolic volume of the braid closure. Consider the unit disk $D\_t$ in the plane $z = t$. As $t$ varies from $0$ to $1$, the points of intersection $D\_t \cap B = \{a\_i^t\}$ move along straight lines at speeds depending on the slope of the $i$'th strand. Here is a lie: when two points $a\_i^t$ and $a\_j^t$ come much closer to each other than they are to any of the other points, then there is a definite contribution to hyperbolic volume. Making this precise (ie, actually true) and then finding a braid $B$ that arranges superlinearly many such meetings would give the desired lower bound. 


One way to do this would be to take $n$ sufficently large, $\epsilon$ correspondingly small, and take the points $a\_i$ to be a generic $\epsilon$--net in $D$. Choose $\sigma$ to be a random permutation. Let $B = B(a, \sigma)$. Take the braid closure and plug everything into SnapPy. I've not tried to do this yet, but it would at least give some data...


**Edit**


Before writing the above, I had the idea of generating a random stick knot using [outer billiards](http://en.wikipedia.org/wiki/Outer_billiard) -- namely, let $P$ and $Q$ be concentric spheres and build a knot by taking segments tangent to $Q$ with endpoints on $P$. This has the virtue that when $Q$ has smallish radius, the expected crossing number will be quadratic. But it seems easier to estimate volume using the braid construction, and it is volume that really matters to us. 


And then... after all this thinking and writing, I started poking randomly around the web and found O'Rourke's [question](https://mathoverflow.net/questions/54412/complexity-of-random-knot-with-vertices-on-sphere) on our very own MO. O'Rourke gives a very simple model for random stick knots: just bounce around in a sphere. The Thurstons suggest that the expected volume grows as $n^{3/2}$.


