Big line or big clique conjecture for planar point sets
Big line or big clique conjecture for planar point sets
Let be a finite set of points in the plane. Two distinct points are visible with respect to if
where is the closed line segment between and . The visibility graph of has vertex set , with two distinct points adjacent exactly when they are visible.
Big line or big clique conjecture. For all integers and there is an integer such that every finite set of at least points in the plane contains either collinear points or pairwise visible points; equivalently, its visibility graph contains a -clique.
This conjecture predicts a dichotomy between arbitrarily large collinear subsets and arbitrarily large cliques in the visibility graph of a planar point set. The source attributes it to KPW; its resolution is not established by the supplied context.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott D. Kominers, Stefan Langerman, Attila Pór and David R. Wood, “Every Large Point Set contains Many Collinear Points or an Empty Pentagon”, arXiv:0904.0262 (2009).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.