Efficient topological triangulations of non-convex polyhedra - MathOverflow

Efficient topological triangulations of non-convex polyhedra

2012-04-03T09:59:56Z

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.

Answer by Misha for Efficient topological triangulations of non-convex polyhedra

2012-04-03T22:44:54Z

Correction: My "answer" below has a fatal mistake, but the idea still could be useful, although, seems to be hard to implement. One could try to use the fact that complexity of a topological triangulation is bounded from below by hyperbolic volume and that for alternating knots/links hyperbolic volume is $O(t)$ where $t$ is the twist number of the alternating diagram (in "most cases" it is just the crossing number). The problem is how to find alternating knot/link diagrams where the crossing number grows quadratically (or, at least, superlinearly) with respect to the number of edges. It is harder than I originally thought and I do not know how to do so.

The original "answer": The answer is negative. I will consider a similar problem: Let $K$ be a polygonal knot in ${\mathbb R}^3$; assume that $K$ has $n$ edges. We will estimate the minimal number of simplices needed to (topologically) triangulate ${\mathbb R}^3$ so that $K$ is contained in the 1-skeleton of the triangulation. By topological triangulation I mean one where simplices are not required to be linear with respect to the standard affine structure of ${\mathbb R}^3$. (Instead of a knot $K$ you would be considering a torus which is the boundary of a tubular neighborhood of $K$, but the size of the linear triangulation of the torus is $O(n)$ and, thus, my setup is equivalent to a special case of yours for knotted tori in ${\mathbb R}^3$.) Assuming that the exterior $ext(K)$ of $K$ is hyperbolic, the number of simplices in this triangulation is bounded from below by the hyperbolic volume of $ext(K)$. Now, suppose that $K$ is an alternating knot and, moreover, projection of $K$ to a generic plane is an alternating knot diagram $D$. (Thus, $ext(K)$ is almost always hyperbolic with the, very rare, exception of an alternating torus knot diagram, due to a result of Menasco.) If you take $K$ so that the vertices $K$ project to points on the unit circle and all edges project to segments of roughly length 2, then the crossing number $c=c(D)$ in $D$ is $O(n^2)$ as projections of all edges of $K$ intersect. Marc Lakenby proved in his "The volume of hyperbolic alternating link complements" paper that the volume of $ext(K)$ (for alternating hyperbolic knot $K$) is $O(t)$, where $t=t(D)$ is the number of "twist regions" in $D$. If $D$ contains no bigons (as in the construction I described with vertices on the unit circle) then $t=c$. Thus, $vol(ext(K))=O(n^2)$ for such knots.

On the other hand, if you assume that your polyhedral surface is bounds, say, a handlebody, then complexity of minimal (topological) triangulation of the handlebody is $O(n)$.

Answer by Sam Nead for Efficient topological triangulations of non-convex polyhedra

2012-04-13T13:35:13Z

The question in the comment was as follows.

Is there an infinite family of (hyperbolic) stick knots whose crossing numbers are quadratic in the number of edges?

The answer is yes. Suppose that $T$ is the $(p,q)$-torus knot, with $2 \leq p < q \leq 2p$. Wikipedia tells us that $T$ has crossing number $(q−1)p$ and has stick number $2q$. Taking $p$ and $q$ close together gives a non-hyperbolic example. Now change a few crossings randomly - that changes the stick number by a small constant and makes the knot hyperbolic, almost surely. If you'd rather, you can instead use twisted torus knots. See the paper "The simplest hyperbolic knots" or the paper "The next simplest hyperbolic knots".

However, neither of these obviously give $O(n^2)$ lower bounds for your original question -- these knots typically have very small hyperbolic volume and small triangulations; hence the name of the two papers I cited.

EDIT - My previous sentence can be made even more concrete. Fixing $n$ there are torus knots with stick number $O(n)$, with crossing number $O(n^2)$ and whose complements only require $O(\log(n))$ tetrahedra to triangulate. See the last paragraph of Agol's answer to this question: http://mathoverflow.net/questions/46149/lower-bound-on-number-of-tetrahedra-needed-to-triangulate-a-knot-complement

Of course, these minimal triangulation do not have the desired boundary patterns. But it does indicate that the statement "large crossing number implies large triangulation" fails rather badly.

Answer by Sam Nead for Efficient topological triangulations of non-convex polyhedra

2012-04-18T20:40:07Z

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 -- 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 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}$.