Edit Question - KnowledgeHub

Title Body

(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 1 and Edge 2 will intersect. Edge 6 will intersect with Edge 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.

Tags (comma-separated) Cancel