On Compatible Matchings

摘要

A matching is compatible to two or more labeled point sets of size n with labels {l,...,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ［2n~(1/2)］edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n~(1/ℓ)). As a corresponding upper bound, we use probabilistic arguments to show that for any l given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n~(2/ℓ+1)) edges. Finally, we show that O(log n) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.