Maximal Length Common Non-Intersecting Paths
Jurek Czyzowicz, Evangelos Kranakis, Danny Kriz̧anc, Jorge Urrutia · Canadian Conference on Computational Geometry · 1996
Given a set P n of n points on the plane labeled with the integers f1; : : : ; ng, an increasing path of P n is a sequence of points i 1 ! : : : ! i k such that the polygonal path obtained by connecting i j to i j+1 , j = 1; : : : ; k \\Gamma 1 is non-self intersecting. We show that any point set on the plane admits an increasing path of length at least p 2n. We also study the problem of finding the longest common increasing path of two convex point sets on the plane and give an O(n 2 log n) time algorithm to find such a path. 1 Introduction Let P n = fp 1 ; : : : ; p n g be a set of n points on the plane. We say that P n supports a planar graph G(V; E) if there is a plane embedding of G(V; E) on the plane in such a way that its vertices are mapped to the elements of P n and its edges to straight line segments connecting pairs of adjacent vertices. Given two point sets P n and Q n , the problem of finding graphs x D'epartement d'Informatique, Universit'e du Qu'ebec `a Hull, Hull...