No label defined (Q4225307)

Let \(P\) be a set of \(2n\) points in the plane in general position. A straight line \(H\) passing through two points of \(P\) is called a halving line of \(P\) if each of the two open half-planes bounded by \(H\) contains \(n-1\) points of \(P\). It is shown that \(P\) admits a perfect matching with pairwise crossing line segments if and only if it has precisely \(n\) halving lines. In this case the matching is unique and consists of exactly those segments between two points of \(P\) whose extensions are halving lines. As a consequence, the authors present an \(O(n\log n)\) time, \(O(n)\) space algorithm which decides whether there exists such a matching of \(P\) and, if so, finds it. For the entire collection see [Zbl 0902.00037].