Thanks, George, for pointing me to your terrific paper! (44MBytes for your 9-page paper must be some sort of a record! I suspect that hi-rez full-color versions of your pictures lurk within this PDF.) It sounds like you were approaching exactly the same problem from a slightly different perspective: that of an artist. I am also trying to build 3D 'watertight' manifolds from triangulated surfaces -- e.g., the binary '.stl' file format -- but my goals aren't aesthetic, but engineering: how to build the strongest/stiffest structures from a minimum of material. I believe that my approach to struts will yield surfaces with perhaps one order of magnitude fewer vertices & triangles than yours, because none of my struts are 'twisted' (twisted struts don't preserve the area of the cross-section). My approach also trivially extends to cylindrical struts with >3 faces; the 'angle bisector' part of the proof below also works for regular n-gons. BTW, the proof below might also enable a consistent 'paint scheme' for the faces of the cylindrical struts, which would be aethetically pleasing. The 'angle bisector' proof would also work for strut cross-sections which are non-regular n-gons, so long as they have (bilateral?) symmetry, because the orientation is preserved across every edge intersection at a vertex. It is interesting that an entire structure made up of O(10^6) vertices/edges/faces may have only 1 degree of freedom, so that the orientation of exactly 1 strut will force the orientation of _all_ of the rest of the struts! I'm going to call my theorem the 'No-Twist' theorem. If you're on the inside of one of these tubes & follow any cyclic path through the structure, you will arrive back where you started without undergoing _any_ net rotations. I would imagine that other mathematicians will be happy to explore networks in which paths exist (especially with regular n-gons) where you undergo a net rotation of 360*i/n for any integer i. This might be useful if some of the 'struts' are in tension -- i.e., they are 'ropes'/'wires' instead of compression struts. I also have the goal of eliminating complex (and very expensive) 'solid geometry' operations, so that I can quickly build O(10^6) sized objects without taking a long time. I believe that I should also be able to pre-compute all of my intersection triangles without having to call upon CSG union/intersection/difference algorithms, but I haven't yet finished those algorithms. --- I conjecture that the number of 'degrees of freedom' = the number of connected components of the undirected graph. Proof sketch. Consider any simple cyclic path in the graph & throw away the rest of the graph (for the moment). Each vertex in the path now has degree exactly 2. But the same 'angle bisector' argument for the triangle (see below) shows that once the angle choice is made for one of the struts incident on the vertex, the same choice is required for the other incident strut. By induction, the choice on one strut constrains the choice on every other strut in the cycle. We thus have at most one consistent labelling for the entire cycle. But can we always make a consistent choice for the entire cycle? Yes, because we can always _triangulate_ the cycle. I.e., if we start from a particular vertex in the cycle, this constrains both incident edges. But we can now shorten the cycle by one edge & one vertex by removing that vertex & both incident edges & installing a new edge between the opposite ends of the removed edges. Eventually, we produce a triangle, which we already know can be consistently labelled. Reversing the steps, we now know that the entire cycle is determined by the rotation of any single strut edge in the cycle. But this means that any one edge incident on the vertex constrains every other edge incident on that vertex, because we can always choose a path that includes both edges. Thus, the entire connected component has at most one degree of freedom, and at least one degree of freedom. It would be neat to _animate_ such an embedded graph by rotating the faces of all the struts in unison. (What kind of gear train would be required inside the vertices in order to achieve this unanimous rotation?) At 09:16 AM 6/4/2013, George Hart wrote:

Henry,

Here is one solution to your problem, but this approach doesn't require right regular cylindrical polyhedra. Permitting more general strut shapes allows for a simple algorithm. It scales well to large graphs as it is based on many small convex hull operations in local neighborhoods:

George Hart, "An Algorithm for Constructing 3D Struts," Journal of Computer Science and Technology, 24:1, 2009, pp. 56-64.

http://jcst.ict.ac.cn:8080/jcst/EN/Y2009/V24/I1%20%20%20%20%20%20%20%20%20/5...

http://www.georgehart.com/rp/Algorithmfor%20Constructing3DStruts.pdf

George http://georgehart.com/

On 6/4/2013 8:53 AM, Henry Baker wrote:

...

I've been hacking some code for building 'networks' in 3D out of 'nodes' and 'links'.

Here's the problem.

I have a very large undirected graph -- e.g., O(10^6) vertices/faces/edges -- that I want to embed in 3D.

I make an assignment of vertices to 3D points, and would then like to 'link' these points together with 'links'/'struts' which are right regular cylindrical polyhedra.

Thus, given points P1=[x1,y1,z1], P2=[x2,y2,z2], I want to 'link' P1 to P2 with a 'strut' whose cross section is a regular n-gon (e.g., equilateral triangle) of some fixed size (e.g., side length = 10 millimeters).

For the moment, I will completely ignore the problem of choosing the 3D locations of the vertices so that the struts do not interfere/intersect -- except where two (or more) struts meet at a vertex node. (This will be easy if I construct the graph embedding in the first place with no such interferences/intersections.)

We thus assume that we have a 'good' embedding of vertices/nodes in 3D such that the struts don't interfere/intersect except at the vertices/nodes themselves.

Note that when we have a 'strut' from P1 to P2, the line down the exact center of this strut goes exactly from P1 to P2.

However, the angles/faces where two such struts meet can be quite complex.

Thus, the only degree of freedom for the strut from P1 to P2 is the _rotation angle_ of the strut around the line from P1 to P2 as the axis of rotation.

I'd like to minimize the complexity (in terms of the number of faces/facets) of the overall structure, which means minimizing the number of faces where the struts come together at the vertices.

Consider one of the simplest examples: a complete graph of 3 vertices joined by 3 edges/links, which I embed in 3D as an equilateral triangle.

I want the links to have cross-sections which are regular n-gons -- e.g., triangles.

I could choose to have the 'flat' part of all three struts on the _outside_ of the big triangle linking the 3 nodes. Each pair of struts would meet at a 60 degree angle and generate no additional faces.

Or I could choose to have the 'edge' part of all three struts on the _ outside_ of the big triangle linking the 3 nodes. Each pair of struts would still meet at a 60 degree angle and generate no additional faces.

But I could choose _any angle_ for one strut around its long axis, and -- so long as I choose the _same angle_ for the other two struts -- I can still arrange for the struts to meet at the vertices/nodes with no additional faces.

I.e., the complete graph of 3 vertices and 3 edges has only 1 degree of freedom.

Q: what happens if the location assignment of the graph to 3D is no longer equilateral? Am I now forced to have additional faces?

A: No, we can still have simple joins. Proof: look at the 3 planes which are the angle bisectors of the embedded triangle. When 2 struts meet at such an angle bisector plane, they intersect the angle bisector plane at the same triangle if their rotation angle about their long axis is the same. Thus, _any_ embedded triangle still has exactly 1 degree of freedom: if we choose the rotation angle of any 1 of the 3 struts, the rotation angles of the other two struts are constrained to be the same.

Q: what happens with more complex objects -- e.g., what happens if I start with a _planar_ graph & use a location assignment that preserves its planarity. What exactly do the nodes look like where the struts come together at random angles?

Q: what happens with non-planar embeddings -- e.g., a graph that looks like a regular (or perhaps non-regular) tetrahedron?

Tom Verhoeff's papers on 'mitering' are incredibly relevant! Thank you. I particularly liked Verhoeff's 'mitered fractal trees', which grow by 2 or 3 way branching to smaller similar blocks set an an angle. This is actually very relevant to building 'fractal beams' which handle compressive loads better than solid beams of the same weight. It should be possible to 'build' a fractal beam using Verhoeff's ideas -- which building process will also minimize the number of vertices/edges/faces. Verhoeff shows that the 'nicest' mitering for vertices of degree 3 can only be done at certain discrete angle combinations -- i.e., once one angle is chosen, there are only a certain integer number of other angles possible. While this is great for art, and Verhoeff shows some spectacular pictures of his results, I can't be so restricted for my engineering application. I have to be able to build much larger structures, which means many more arbitrary angles to deal with. While I would like my struts to be approximations to cylinders of circular orthogonal cross-section, these n-gons don't have to be regular. The elliptical intersections of equal-sized circular struts can be approximated by any reasonably distributed n points on the boundary of the ellipse. --- How's this for a recursive marking algorithm to 'triangularize' a ball-and-cylinder embedded graph? Pick any strut to start. Pick any point on the surface of the strut near the middle -- i.e., not so close to either end that it might end up 'inside' the end-cap of the strut end. Draw a line along the surface of the strut in both directions, parallel to the long axis of the strut. Consider one end of the strut, which will meet other struts at a vertex. Pick one of the other struts. Compute the intersection of that strut with the line we've just constructed. Make a new line on this new strut. Continue this process with the new line by looking at where it intersects with another strut at the other end of this new strut. If we ever run into one of our previous lines, we terminate this branch and resume with the other end of line segments we've already constructed. Based on our No Twist theorem, we know that we are certain to run into ourselves again after visiting all of the struts on a path exactly once. If we've already resumed all of the line segments, then we've completely closed all loops, and we should have visited every strut and every vertex of this connected component. Indeed, there should be just one line segment through every strut. Note that these lines do _not_ form an Euler path, because we've made no provision for retracing each line segment more than once. We now take our starting point & rotate it by 360/n about the long axis of the strut on which it is located. We then perform our entire process again. Continuing similarly for another n-2 'tours' of the structure, and we should now have a complete marking. Alternatively, we could have our line along the strut deviate from being parallel to the strut axis by a very small amount, in which case the sequence of line segments might not 'meet' itself until it had visited every strut multiple times at multiple places around its circumference. At 11:04 AM 6/4/2013, George Hart wrote:

Henry,

If you are interested in minimizing the number of triangles in the surface, be aware that the sides of an n-gon prism are represented in the STL file as 2n triangles, which is identical in cost to an n-gon antiprism. So constraining your algorithm to prismatic struts does not help with the sides of the struts and can hurt if extra facets are needed to close up the surface around vertices.

If you are interested in minimizing the number of triangles in the boundary, see this earlier paper, which uses a duality-based approach that gives surprisingly small STL files for high-genus graph embeddings:

George Hart, "Solid-Segment Sculptures," Proceedings of Colloquium on Math and Arts, Maubeuge, France, 20-22 Sept. 2000, and in Mathematics and Art, Claude Brute ed., Springer-Verlag, 2002, pp. 17-28.

http://georgehart.com/solid-edge/solid-edge.html

For the "No-twist" theorem of mitered prismatic struts in a loop, see several papers by Tom Verhoeff in the Proceedings of the Bridges Conference from 2008-2011. He has also made some rotating animations of the type you suggest:

http://www.win.tue.nl/~wstomv/publications/

George http://georgehart.com/

My 'proof sketch' was all wet. Basically, the lengths of the struts don't matter, so we're really talking about a sequence of 3D rotations (think Quaternions). In 2D, any sequence of rotations preserves the axis, which is always in the same direction. In 3D, we can achieve all manner of twists with a sequence of rotations about different axes. A product of quaternions can be collapsed into a single quaternion uniquely because quaternion multiplication is associative. No Twist theorem applies only to planar cycles where all the twists have parallel axes. So George Hart & Tom Verhoeff are correct; in particular, it is easy to make a 'Mobius pipe' in 3D on which you can draw a line along all the struts & elbows & the line will traverse all of the struts twice -- once on either side. At 10:27 AM 6/4/2013, Henry Baker wrote:

I conjecture that the number of 'degrees of freedom' = the number of connected components of the undirected graph.

Proof sketch. Consider any simple cyclic path in the graph & throw away the rest of the graph (for the moment). Each vertex in the path now has degree exactly 2. But the same 'angle bisector' argument for the triangle (see below) shows that once the angle choice is made for one of the struts incident on the vertex, the same choice is required for the other incident strut. By induction, the choice on one strut constrains the choice on every other strut in the cycle. We thus have at most one consistent labelling for the entire cycle.