Large harmonic sets of noncrossing edges for n randomly labeled vertices in convex position

Consider a set of n points in the plane in convex position, where each point has an integer label from {0,1,..., n - 1}. This naturally induces a labeling of the edges: each edge (i,J) is assigned the label i %2bj, modulo n. We propose algorithms for finding large noncrossing harmonic matchings or paths, i.e., the matchings or paths in which no two edges have the same label. When the point labels are chosen uniformly at random, and independently of each other, our matching algorithm with high probability delivers a nearly-perfect matching, a matching of size n/2 - O(n1/3 In n). We show that, in sharp contrast, a near-perfect path is unlikely: with high probability the length of the longest path is below 0.96n. In a series of computer experiments, one of our algorithms invariably found a path of length above 0.76n, and the likely path length for our empirically second best algorithm is proved to be above 0.66n. © 2006 Wiley Periodicals, Inc.

VIVO