Subset selection problems in planar point sets

Given a finite point set satisfying condition A, the subset selection problem asks, how large of a subset satisfying condition B can be extracted? Problems of this nature are notoriously difficult and have attracted extensive study. In this paper, we make progress on three instances of subset selection problems in planar point sets. Let n, s ∈ N with n ≥ s, and let P ⊆ R$^2$ be a set of n points, where at most s points lie on the same line. Firstly, we select a general position subset of P, i.e., a subset containing no 3 points on the same line. This problem was proposed by Erdős under the regime when s is a constant. For s being non-constant, we give new lower and upper bounds on the maximum size of such a subset. In particular, we show that in the worst case such a set can have size at most O(n5/6+o(1)/√s) when 3 ≤ s ≤ n$^{1/3}$ and O(n/s) when n$^{1/3}$ ≤ s ≤ n. Secondly, we select a monotone general position subset of P, that is, a subset in general position where the points are ordered from left to right and their y-coordinates are either non-decreasing or non-increasing. We present bounds on the maximum size of such a subset. In particular, when s = Ω(√n), our upper and lower bounds differ at most by a logarithmic factor. ... mehrLastly, we select a subset of P with pairwise distinct slopes. This problem was initially studied by Erdős, Graham, Ruzsa, and Taylor on the grid. We show that for s = O(√n) such a subset of size Ω((n/ log s)$^{1/3}$) can always be found in P. When s = Θ(√n), this matches a lower bound given by Zhang on the grid. As for the upper bound, we show that in the worst case such a subset has size at most O(√n) for 2 ≤ s ≤ n$^{3/8}$ and O((n/s)$^{4/5}$) for n$^{3/8}$ ≤ s = O(√n). The proofs use a wide range of tools such as incidence geometry, probabilistic methods, the hypergraph container method, and
additive combinatorics.