Crossing families (Q1330788)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Crossing families
scientific article

    Statements

    Crossing families (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    11 August 1994
    0 references
    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.
    0 references
    Erdős-type problems
    0 references
    Ramsey theory
    0 references

    Identifiers