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

József Balogh, Boris Pittel, Gelasio Salazar

Research output: Contribution to journalArticlepeer-review

Abstract

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 +j, 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.

Original languageEnglish (US)
Pages (from-to)105-130
Number of pages26
JournalRandom Structures and Algorithms
Volume30
Issue number1-2
DOIs
StatePublished - Jan 1 2007

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Large harmonic sets of noncrossing edges for n randomly labeled vertices in convex position'. Together they form a unique fingerprint.

Cite this