Adding to my post below titled Embroidermation: test 1, my co-lunatic Theo Gray shares an animation of the Chinese Postman traveling every path, instructing the machine how to stitch the design:
And here is a screen shot of what he did in Mathematica to get there:
Wow!!! Thanks for sharing this! So cool. That’s one continuous line, eh?
The elegance and power of a good algorithm. Such beauty. I am awestruck.
A fantastic beast. Incidentally, I’m not sure of the difference, if any, between the Chinese Postman Problem and the Travelling Salesman Problem. Can anyone help? I’ve seen the Mona Lisa done as the latter here.
Wow. I wish I was better with math.
Nina, I sent you an email. Do you still check the yahoo account listed on the sidebar of your site?
I loved seeing all of your work thanks to Amy’s feature of you today! I have a fine art background and my husband is an animator so it’s great to see the two worlds collide. When I started quilting I had to get over all of that fine art baggage so Air/Nude really speaks to me. I can’t wait to see what you do next.
Khurram: The difference between a traveling salesman and a Chinese postman is that a traveling salesman wants to visit every node (house) once and do that traveling the minimum possible distance. A Chinese postman wants to walk every path between all the houses at least once, duplicating the minimum number of paths. It is easily proven that there exist graphs for which it is not possible to do this without traveling at least some of the paths more than once, so the goal is to minimize the number of times that’s necessary.
The Chinese postman problem is also known as the street-sweeper problem, which makes the motivation more obvious: The street sweeper wants to sweep every street, but doesn’t want to waste time sweeping the same street twice.
In this application, each line is an edge of the graph, and each point where three or more lines meet is a node. (Two lines meeting is just a line with a bend in it, which is still only one path.)
Thanks for explaining the difference, Theodore.