Halving lines and perfect cross-matchings
János Pach, József Solymosi · Contemporary mathematics - American Mathematical Society · 1999
It is shown that a set P of 2n points in general position in the plane admits a perfect matching with pairwise crossing segments if and only if it has precisely n halving lines. As a consequence, one can give a O(n log n)-time algorithm which decides whether there exists such a matching in P and, if so, finds it. 1 Preliminaries Let P = fp 1 ; p 2 ; : : : ; p 2n g be a set of 2n points in the plane in general position, i.e., no three points are collinear. A line p i p j is said to be a halving line of P if both open half-planes bounded by p i p j contain precisely n \\Gamma 1 points. The number of halving lines of P is denoted by h(P ). Taking an arbitrary line through any point of P and turning it around by at most 180 degrees, it always arrives at a position where it becomes a halving line. Thus, we have h(P ) n, and equality holds, e.g., when P is the vertex set of a convex 2n-gon. It is an intriguing open problem to determine the asymptotic behavior of h(n) = max P h(P ), w...