# Knots from graphs

Ryan McGuire
Ranch Hand
Posts: 1085
4
How about this for a problem to try to solve programmatically.

Given a continuous graph, determine whether it it would form a knot if you pulled the two ends.

Example 1: In its initial position, a string goes from (0,2) to (3,2) to (1,1) to (2,3) to (2,0), alternating over and under at each intersection. If you pull the two ends directly away from each other, the string would form an overhand knot.

Example 2: The string has the same basic initial position as in Example 1, but it goes over-over-under-under-under-over along the path. Pulling on the ends would produce no knots.

I can see a number of hurdles to pass:
• Define the question more rigorously.
• List any specific knots we might to identify by name. For instance, I could see the output being one of [no knot, overhand, figure 8, something else]
• Figure out a good input "language"
• Develop an algorithm to figure out the answer.

• Thoughts?
[ September 14, 2007: Message edited by: Ryan McGuire ]

Arjun Shastry
Ranch Hand
Posts: 1901
1
In the second example,string will go 'Over--->Over--->Under'.only three intersections,correct?

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I think it might make sense to simply use three dimensions for all vertices. Then you can input a list of points which describe any possible 3-D knot. Any input for which two lines intersect is invalid - the input must keep the lines far enough apart that they don't appear to intersect. There could be numeric roundoff issues here - for simplicity, let's say input lines can come no closer than a distance of 0.1.

A simple input language might be:

Each line represents a single point. A line consists of three numbers in decimal format, separated by commas. A blank line signals the end of a given string (which may or may not be a not. Input may contain multiple strings to solve. Two blank lines signals the end of all strings.

Ryan McGuire
Ranch Hand
Posts: 1085
4
Originally posted by Arjun Shastry:
In the second example,string will go 'Over--->Over--->Under'.only three intersections,correct?

Yes, there are three intersections, but each intersection is "visited" twice. That's why there's [over|under]{6}.

Of course the over or under for one segment of the string at an intersection determines the other over/under for the other segment. For instance, in both of my examples if the fourth over/under must be the opposite of the first. So the second three convey no additional information.

Originally posted by Jim Yingst:
I think it might make sense to simply use three dimensions for all vertices.

Yes, but...
It's harder to draw a input case on (2-D) paper and be sure to get the z coordinates correct. It would also be more difficult to modify one input case into a similar one with just the overs and unders changed. Impossible? Of course not -- just harder.

e.g. My original first example is just five 2-D points plus (as discussed above) three bits.
(0,2)
(3,2)
(1,1)
(2,3)
(2,0)
1,0,1

Changing that to the second example involved just changing the bit from 1,0,1 to 1,1,0

I guess I'm of the opinion that programs should be made to make the user's life as easy as possible, even if it involves quite a bit of extra programming.