I have two arrays, each containing a different ordering of the same set of integers. Each integer is a label for a point in which two closed paths intersect in the plane. The two arrays are interpreted as giving the circular ordering (in clockwise order) of points along each of two closed paths in the plane, with no particular starting point. The two paths intersect with each other as many times as there are points in the arrays, but a path may not self-intersect at all. How do I determine, from these two arrays, whether it is possible to draw the two paths in the plane without self-crossings? (The integer labels have no inherent meaning.)
Example 1: A = {3,4,2,1,10,7} and B = {1,2,4,10,7,3}: it is possible
Example 2: A = {2,3,0,10,8,11} and B = {10,2,3,8,11,0}: it is not possible.
Try it by drawing a circle, with 6 points labelled around it according to A, then attempt to connect the 6 points in a second closed path, according to the ordering in B, without crossing the new line you are drawing. (I believe it makes no difference to the possibility/impossibility of drawing the line whether you start by exiting or entering the first loop.) You will be able to do it for example 1, but not for example 2.
I am currently using a very elaborate method where I look at adjacent pairs in one array, e.g. in Example 1, array A is divided into {3,4}, {2,1}, {10,7}, then I find the groupings in the array B as partitioned by the two members listed in each case:
{3,4} --> {{1,2}, {10,7}} {2,1} --> {{4,10,7,3}, {}} {10,7} --> {{3,1,2,4}, {}}
and check that each pair on the left-hand-side finds itself in the same grouping of the right-hand-side partition in each of the other 2 rows. Then I do the same, offset by one position:
{4,2} --> {{10,7,3,1}, {}} {1,10} --> {{2,4}, {7,3}} {7,3} --> {{1,2,4,10}, {}}
Everything checks out here.
In Example 2, though, the method shows that it is impossible to draw the path. Among the "offset by 1" pairs from array A we find {10,8} causes a partition of array B into {{2,3}, {11,0}}. But we need 11 and 2 to be in the same grouping, as they are the next pair of points in array A.
This idea is unwieldy, and my implementation is even more unwieldy. I'm not even 100% convinced it always works. Could anyone suggest an algorithm for deciding?
