Crossing families (Q1330788)

Among the line segments determined by \(n\) points (in general position) in the plane there are always at least \(\sqrt{n/12}\) which are pairwise intersecting (in the interior), and at least \(\sqrt{n/12}\) which are pairwise disjoint. (The second part is shown to be equivalent to the first one. Furthermore, this proposition also holds if the line segments between the points of two sets of size \(n\) are considered.) This statement is proved by constructing two sets of \(\sqrt{n/12}\) points each which have the property that the (unbounded) lines determined by the points of one set do not meet the convex hull of the other set (and vice versa), and by appropriately joining the points of these two sets. (The time required by this construction is \(O(n \log n)\).) The authors suspect that their lower bound is far from optimal. Generalizations to higher dimensions are discussed briefly.