Algorithm for Least Edge Intersections

Question

(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,

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

Answer 1

Assuming that no element is repeated in a single array, this is simply longest increasing subsequence.

Without loss of generality, assume that the first array, A1, is just [1, 2, 3, ..., n]. This transformation can be done in O(n) with a hash-set, or O(nlogn) with a BST.

Note that our set has a crossing if and only if it contains i and j with i < j but j appearing before i in the second array A2 (we know since i < j that i appears before j in A1).

Then if a set has no crossing it clearly corresponds to an increasing subsequence of A2 and vice versa.

Longest increasing subsequence has a simple O(n^2) solution and a slightly more complex O(nlogn) solution.