Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 804.52010
Autor: Aronov, B.; Erdös, Paul; Goddard, W.; Kleitman, Daniel J.; Klugerman, M.; Pach, János; Schulman, L.J.
Title: Crossing families. (In English)
Source: Combinatorica 14, No.2, 127-134 (1994).
Review: 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.
Reviewer: P.Schmitt (Wien)
Classif.: * 52C10 Erdoes problems and related topics of discrete geometry
68Q20 Nonnumerical algorithms
Keywords: Erdös-type problems; Ramsey theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag