# General Position Subset Selection in Line Arrangements +
## 1 Introduction  
A set of points in the plane is said to be in _general position_ if no three points are collinear. The problem of selecting a large subset of points from a \(k\times k\) grid of integer points with no three points collinear (i.e., in general position) goes back more than 100 years; see, for example, [1, 2] (Ch. 10). In particular, it is not known if one can always select \(2k\) points from the \(k\times k\) grid so that no three points are collinear [1]. A key quantity in the process of selecting a large subset from an input set of points is the number of _collinear triples_ in the set. [PERSON] and [PERSON] [3] obtained the following upper bound on this number. The proof relies on the classical points and line incidence bound due to [PERSON] and [PERSON] [4]; see also [5] (Chap. 10) and [6] for a modern approach to this topic. The special case \(\ell=O(\sqrt{n})\) in the lemma can also be found in [7] or in [8] (p. 313). **Lemma 1** ([3]). : _Let \(P\) be a set of \(n\) points in the plane with at most \(\ell\) collinear. Then, the number of collinear triples in \(P\) is \(T=O(n^{2}\log\ell+\ell^{2}n)\). In particular, if \(\ell=O(\sqrt{n})\), then \(T=O(n^{2}\log\ell)\)._  
By applying the above lemma together with a lower bound on the independence number of a hypergraph obtained by [PERSON] [9], [PERSON] and [PERSON] [3] obtained the following result. **Theorem 1** ([3]). : _Let \(P\) be a set of \(n\) points in the plane with at most \(\ell\) collinear. Then, \(P\) contains a subset of \(\Omega\Big{(}n/\sqrt{n\log\ell+\ell^{2}}\Big{)}\) points in general position. In particular, if \(\ell=O(\sqrt{n})\), then \(P\) contains a subset of \(\Omega\Big{(}(n/\log\ell)^{1/2}\Big{)}\) points in general position._  
A cursory examination of the above lower bound shows that if the input set has a large subset of points in general position (of, say, nearly linear size), then the above guarantee is roughly a factor of \(\sqrt{n}\) smaller than the truth. Given a set \(P\) of points in the plane, the General Position Subset Selection problem (GPSS, for short), is that of finding a maximum-size subset of points in general position. The problem is known to be NP-complete and APX-hard, and the current best approximation for the problem is a greedy algorithm due to [PERSON] (2010) (Chap. 3), achieving a ratio of \(\Omega\Big{(}\mathsf{OPT}^{-1/2}\Big{)}=\Omega(n^{-1/2})\); here, \(\mathsf{OPT}\) is the cardinality of an optimum solution to GPSS. See also ([PERSON] and [PERSON], 2011) (Chap. 9) and ([PERSON] and [PERSON], 2011) for further aspects of this problem and ([PERSON] and [PERSON], 2011) for basic notions in complexity and approximation. Throughout this paper, ALG denotes the cardinality of the solution to GPSS computed by an algorithm under consideration. As in ([PERSON] and [PERSON], 2011), here, we follow the convention that the approximation ratio of an algorithm for a maximization problem is less than \(1\). Throughout this paper, all logarithms are in base 2. **Our results. **  
(I) For a set \(P\) of \(n\) points in the plane, consider the ratio (sometimes also called _spread_)  
\[D(P)=\frac{\max\{|ab|\colon a,b\in P,a\
eq b\}}{\min\{|ab|\colon a,b\in P,a \
eq b\}},\]  
where \(|ab|\) is the Euclidean distance between points \(a\) and \(b\). Since the general position property is unaffected by scaling, we may assume, without loss of generality, that \(\min\{|ab|\colon a,b\in P,a\
eq b\}=1\). In this case, \(D(P)=\max\{|ab|\colon a,b\in P,a\
eq b\}\) is the diameter of \(P\). A standard disk packing argument shows that if \(|P|=n\), then \(D(P)\geq\alpha_{0}\,n^{1/2}\), where  
\[\alpha_{0}:=2^{1/2}3^{1/4}\pi^{-1/2}\approx 1.05, \tag{1}\]  
provided that \(n\) is large enough; see ([PERSON] and [PERSON], 2011) (Prop. 4.10). On the other hand, a \(\sqrt{n}\times\sqrt{n}\) section of the integer lattice shows that this bound is tight up to a constant factor.