Efficient topological triangulations of non-convex polyhedra - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T20:58:09Z http://mathoverflow.net/feeds/question/92983 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92983/efficient-topological-triangulations-of-non-convex-polyhedra Efficient topological triangulations of non-convex polyhedra JeffE 2012-04-03T09:59:56Z 2012-04-18T23:28:51Z <p><strong>Does every polyhedron in $\mathbb{R}^3$ with $n$ triangular facets have a <em>topological</em> triangulation with complexity $O(n)$?</strong></p> <p>Suppose $P$ is a non-convex polyhedron in $\mathbb{R}^3$ with $n$ triangular facets, possibly with positive genus. A <em>topological</em> 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 <em>geometric</em> triangulations, every simplex is the convex hull of its vertices.</p> <p>Results of <a href="http://www.cs.princeton.edu/~chazelle/pubs/BoundsSizeTetrahedral.pdf" rel="nofollow">Chazelle and Shouraboura</a> imply that every polyhedron has a geometric triangulation with complexity $O(n^2)$. Moreover, a classical construction of <a href="http://www.cs.princeton.edu/~chazelle/pubs/ConvexPartitionPolyhedra.pdf" rel="nofollow">Chazelle</a> implies that the $O(n^2)$ bound is is optimal in the worst case, even when the genus is zero.</p> <p>But we can get tighter bounds for topological triangulations, at least for genus-zero polyhedra. If $P$ has genus zero, <a href="http://en.wikipedia.org/wiki/Steinitz%27s_theorem" rel="nofollow">Steinitz's theorem</a> implies that there is a <em>convex</em> polyhedron $Q$ that is combinatorially equivalent to $P$. <a href="http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1085499/" rel="nofollow">Alexander's extension of the Schönflies theorem</a> implies that the interiors of $P$ and $Q$ are both homeomorphic to open balls. Thus, applying a suitable homeomorphism to a minimal <em>geometric</em> triangulation of $Q$ gives us a <em>topological</em> triangulation of $P$ with complexity $O(n)$. (Alternatively, we can triangulate $P$ by joining an arbitrary interior point to every facet.)</p> <p>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.</p> <p>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 <em>topological</em> triangulation of $S^3$ with complexity $O(n)$ that includes $K$ in its 1-skeleton? Again, if we insist on <em>geometric</em> triangulations, $\Theta(n^2)$ tetrahedra are always sufficient and sometimes necessary, even if $K$ is unknotted.</p> <p><strong>Added for bounty (Apr 13):</strong> 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.</p> http://mathoverflow.net/questions/92983/efficient-topological-triangulations-of-non-convex-polyhedra/93048#93048 Answer by Misha for Efficient topological triangulations of non-convex polyhedra Misha 2012-04-03T22:44:54Z 2012-04-05T16:03:37Z <p>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. </p> <p>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 <a href="http://arxiv.org/abs/math.GT/0012185" rel="nofollow">"The volume of hyperbolic alternating link complements"</a> 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. </p> <p>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)$. </p> http://mathoverflow.net/questions/92983/efficient-topological-triangulations-of-non-convex-polyhedra/93957#93957 Answer by Sam Nead for Efficient topological triangulations of non-convex polyhedra Sam Nead 2012-04-13T13:35:13Z 2012-04-17T14:55:33Z <p>The question in the comment was as follows.</p> <blockquote> <p>Is there an infinite family of (hyperbolic) stick knots whose crossing numbers are quadratic in the number of edges?</p> </blockquote> <p>The answer is yes. Suppose that $T$ is the $(p,q)$-torus knot, with $2 \leq p &lt; 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 <em>twisted torus knots</em>. See the paper "The simplest hyperbolic knots" or the paper "The next simplest hyperbolic knots". </p> <p>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. </p> <p>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: <a href="http://mathoverflow.net/questions/46149/lower-bound-on-number-of-tetrahedra-needed-to-triangulate-a-knot-complement" rel="nofollow">http://mathoverflow.net/questions/46149/lower-bound-on-number-of-tetrahedra-needed-to-triangulate-a-knot-complement</a></p> <p>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. </p> http://mathoverflow.net/questions/92983/efficient-topological-triangulations-of-non-convex-polyhedra/94458#94458 Answer by Sam Nead for Efficient topological triangulations of non-convex polyhedra Sam Nead 2012-04-18T20:40:07Z 2012-04-18T23:28:51Z <p>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. </p> <p><strong>Stick braids</strong></p> <p>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 <em>stick braid</em>.</p> <p>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. </p> <p><strong>Hyperbolic volume</strong></p> <p>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. </p> <p>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...</p> <p><strong>Edit</strong></p> <p>Before writing the above, I had the idea of generating a random stick knot using <a href="http://en.wikipedia.org/wiki/Outer_billiard" rel="nofollow">outer billiards</a> -- 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. </p> <p>And then... after all this thinking and writing, I started poking randomly around the web and found O'Rourke's <a href="http://mathoverflow.net/questions/54412/complexity-of-random-knot-with-vertices-on-sphere" rel="nofollow">question</a> 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}$.</p>