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/