(Before anyone asks, it's not homework.)
Say you have 2 Arrays y0 and y1 where
y0 = [1,2,3,4,5,6] and
y1 = [2,1,6,3,4,5]
Notice y0[0] = y1[1] = 1, it essentially means y0[0] is connected to y1[1]. Similarly, y0[2] = y1[3] = 3 so they are "connected" as well.
(Image courtesy : belisarius)
Each element in one array has a corresponding entry in the second array. Imagine each element in the array as a vertex, and these connections as Edges being drawn from one array to the other.
I need to find a set of edges (of maximum size) such that none of the "edges" (or lines) will intersect.
In the above example, notice,
Edge 1andEdge 2will intersect.Edge 6will intersect withEdge 3, Edge 4, Edge 5.
Therefore, the solution can be be 1,3,4,5 or 2,3,4,5 (size = 4) since none of those lines will intersect each other. There can be multiple solutions, but I need just one.
My Question, Is there any known CS Problem that resembles this? What algorithm should i be using?
I've tried to explain my problem with an example, however, incase it's still not clear i'll clarify any queries. Thanks in advance.