Improved bound in the proof for k=5 and arbitrary l (re: Big Line or Big Clique in Planar Point Sets)

cibulka — Tue, 25 Sep 2012 16:27:59 +0200

In their proof of the case and arbitrary , Abel et al. [ABBCDHKLPW] proved a doubly exponential upper bound on the number of points that guarantees the occurrence of an -tuple of collinear points or a -tuple of points with no other point in their convex hull (an empty pentagon). The upper bound on was improved by Barát et al. [BDJPSSVW] to .

[BDJPSSVW] János Barát, Vida Dujmović, Gwenaël Joret, Michael S. Payne, Ludmila Scharf, Daria Schymura, Pavel Valtr, and David R. Wood. Empty pentagons in point sets with collinearities, arxiv:1207.3633, 2012.

Big Line or Big Clique in Planar Point Sets

David Wood — Tue, 25 Sep 2007 15:41:13 +0200

Author(s): Kara; Por; Wood

Subject: Geometry

Let be a set of points in the plane. Two points and in are visible with respect to if the line segment between and contains no other point in .

Conjecture For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.

Open Problem Garden - Big Line or Big Clique in Planar Point Sets - Comments

Improved bound in the proof for k=5 and arbitrary l (re: Big Line or Big Clique in Planar Point Sets)

Big Line or Big Clique in Planar Point Sets