TR-96-16: Maximal Length Common Non-Intersecting Paths

Given a set Pn of n points on the plane labeled with the integers {1… n} an increasing path of Pn is a sequence of points i1 < … < ik such that the polygonal path obtained by connecting ij to ij+1, j = 1… k-1 is non-self intersecting. We show that any point set on the plane admits an increasing path of length at least p2n. We also study the problem of nding the longest common increasing path of two convex point sets on the plane and give an O(n2 log n) time algorithm to nd such a path.

TR-96-16.pdf