Archived

This topic is now archived and is closed to further replies.

Draw a cube with one continous line?

This topic is 5499 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, Since my last post, I''ve gotten my little renderer working (Some initialisation problems dogged my earlier version) and added an optimization or two (sin and cos values are now stored in lookup tables). I know want to pose a math-theory sort of question. Is it possible to draw a cube, with 8 vertexes, as one single continuous line without overwriting a previous line? I don''t think so, because the way I see it:- At the starting vertex, you have three choices for the vertex to draw to. For each consecutive vertex, you have two choices. Vertex 0, three choices: 1, 3, 4 Vertex 1, two choices: 2, 5 Vertex 2, two choices: 3, 6 Vertex 3, two choices: 0, 7 Vertex 4, two choices: 5, 0 Vertex 5, two choices: 6, 1 Vertex 6, two choices: 7, 2 Vertex 7, two choices: 4, 3 The best path that I think is possible is:- 0, 1, 2, 3, 0, 4, 5, 6, 7, 4 (9 out of 12 edges drawn) Is this correct? If it is, could someone come up with the relevant complex maths so that I can go "ooh" and "aah" at it?

Share this post


Link to post
Share on other sites
If you think of it as a problem of representing the cube as a multigraph and attempting to construct an Euler circuit, it''s easy to see that it''s impossible, because each vertex of a multigraph must have an even degree in order to construct an Euler circuit, and vertices of the multigraph for a cube all have degree 3.

For a related problem, look up the famous Konigsberg bridge problem.

j

Share this post


Link to post
Share on other sites
All nodes must be even only if you want a circuit. The start and end nodes of the graph can be odd. In short, a graph can be drawn if and only if it has 0, 1 or 2 odd genus nodes. Induction gives a formal proof (another of Euler's).

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley



[edited by - Paradigm Shifter on November 22, 2002 10:43:58 AM]

Share this post


Link to post
Share on other sites
Heres a simple way to see that it is impossible. There are 3 ways in or out of any given vertex. When you start at any vertex, and go to another, the one you moved to now has 2 ways in/out. When you take one of these ways out, it now has 1 way back in, and no way out. That means that you must end at that point. However, when you move away from that vertex you are now at, it becomes the same way. Since you cannot end in 2 places, its impossible.

Share this post


Link to post
Share on other sites