Message Boards Message Boards

0
|
3943 Views
|
9 Replies
|
16 Total Likes
View groups...
Share
Share this post:

Finding shortest tour of the vertices of a truncated icosahedron?

How would I approach this problem in Mathematica? I'm actually trying to route a string of lights, either to the vertices or to the edges.

POSTED BY: David Gustavson
9 Replies

Thank you all!

That looks like the right solution. Now I have to build a frame with light sockets in the middle of each edge.

I'll be 3D printing for a while!

I have 100 LEDs on hand, individually controllable, with a Teensy computer chip to drive them. I'm going to need to step through the Graph3D so I can keep my place as I go!

POSTED BY: David Gustavson
Posted 2 years ago

I'm wondering if there's a way to find a path that follows every edge?

It looks to me that FindPostmanTour[] is what's wanted:

Graph3D[DirectedEdge @@@ First[FindPostmanTour[PolyhedronData["TruncatedIcosahedron", "Skeleton"]]]]
POSTED BY: J. M.

@J. M. : This definitely is the ultimate solution (+1) - thanks for sharing!

enter image description here

POSTED BY: Henrik Schachner

Thank you, that's just what I wanted. Amazing! But now I'm wondering if there's a way to find a path that follows every edge? Clearly some edges have to be covered twice.

POSTED BY: David Gustavson

... that's just what I wanted.[...] But now I'm wondering if there's a way to find a path that follows every edge?

Hmm - interesting problem! One simple approach might be to create points along the edges ...

lineEndPts = N[First /@ PolyhedronData["TruncatedIcosahedron", "Lines"]];
linePts = DeleteDuplicates@Flatten[Subdivide[#1, #2, 10] & @@@ lineEndPts, 1];
Graphics3D[Point[linePts]]

enter image description here

... and then calculate the shortest tour along these points:

{length, order} = FindShortestTour[linePts];
gr = PolyhedronData["TruncatedIcosahedron", "Graphics3D"];
Graphics3D[{List @@ gr, Red, Thick, Line[1.05 linePts[[order]]]}]

enter image description here

If you can live with the fact that some of the edges are not covered in one go, then this might serve as a solution.

POSTED BY: Henrik Schachner

It might be sufficient just to add midpoints, provided it is done as a graph (so midpoints can only connect to their two vertex neighbors).

POSTED BY: Daniel Lichtblau

Here is one way:

pts = N@PolyhedronData["TruncatedIcosahedron", "VertexCoordinates"];
{length, order} = FindShortestTour[pts];
gr = PolyhedronData["TruncatedIcosahedron", "Graphics3D"];
Graphics3D[{List @@ gr, Red, Arrow /@ Partition[1.05 pts[[order]], 2, 1]}]

enter image description here

POSTED BY: Henrik Schachner

This is nice. But in general I think you'd want "Skeleton" instead of the vertex coordinates, to enforce that only edges be used. Sere second Basic Example on the ref guide page forFindShortestTour`.

Also it is possible that the poster would really want to use FindHamiltonianPath instead.

POSTED BY: Daniel Lichtblau

Yes, this seems to be the better idea for this case, as - if vertices are numbered accordingly - it gives a plan on how to proceed:

graph = Graph[PolyhedronData["TruncatedIcosahedron", "Skeleton"], VertexLabels -> Automatic];
(* path from vertex 9 to vertex 11 - as an example: *)
hp = FindHamiltonianPath[graph, 9, 11];
HighlightGraph[graph, PathGraph[hp], EdgeShapeFunction -> ({Thickness[.02], Line[#]} &)]

enter image description here

POSTED BY: Henrik Schachner
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract