# General Position Subset Selection in Line Arrangements +
## 2 Subset Selection in Dense Lattice Point Sets  
In this section, we prove Theorem 2. First, we introduce the setup.  
For a positive integer \(m\), the \(m\times m\) grid is the set of points in the plane \(G_{m}=\{(x,y)\colon x,y\in\{0,1,\ldots,m-1\}\). We have \(|G_{m}|=m^{2}\). Following [19], let \(k(m)\) denote the minimum number of colors in a coloring of the points in \(G_{m}\) such that no three collinear points are monochromatic. Since no three points in a single row or column can receivethe same color, we have \(k(m)\geq m/2\). It was shown by [PERSON] [19] that for any \(\varepsilon>0\), \(k(m)\leq(2+\varepsilon)m\) for every \(m\geq M(\varepsilon)\). Among other facts, this is based on the fact that for any \(\varepsilon>0\), there exists a prime between \(m\) and \((1+\varepsilon)m\), for every \(m\geq M(\varepsilon)\). A non-asymptotic result, more convenient for small \(m\), is that there exists a prime between \(m\) and \(6m/5\), for every \(m\geq 25\)[20]. (And by the well-known Bertrand-Chebyshev theorem, there exists a prime between \(m\) and \(2m\), for every \(m\).)  
We briefly recall [PERSON]'s argument [19] relying on a construction of [PERSON] [21]. Let \(p\geq m\) be a prime; in practice we may pick the smallest prime at least \(m\) or a prime at least \(m\) that is close to \(m\). For any integer \(i\), let  
\[V_{i}=\{(x,(x^{2}\bmod p)+i)\colon x=0,1,\ldots,m-1\}.\]  
Note that \(|V_{i}|=m\), and that \(V_{i}\) may be _not_ contained in \(G_{m}\); refer to Figure 1. A Vandermonde determinant calculation shows that \(V_{i}\) is in general position for every \(i\in\mathbb{Z}\). Moreover, \(V_{i}\cap V_{j}=\emptyset\) whenever \(i\
eq j\). Each point \((x,y)\in G_{m}\) is in \(V_{i}\), where \(i=y-(x^{2}\bmod p)\). Since  
\[1-p=0-(p-1)\leq y-(x^{2}\bmod p)\leq m-1,\]  
the union of the \(m+p-1\) sets \(V_{i}\) over \(i=1-p,\ldots,m-1\) consists of \(m+p-1\) color classes, where each class is in general position. That is, \(G_{m}\) can be covered by \(m+p-1\)\(m\)-element point sets in general position. As mentioned in the previous paragraph, \(m+p-1\leq(2+\varepsilon)m\) for every \(m\geq M(\varepsilon)\), or \(m+p-1\leq 11m/5\) for every \(m\geq 25\), as needed.  
Proof of Theorem 2.: Since \(P\) is \(\alpha\)-dense, we may assume that \(P\subseteq G_{m}\), where \(m=\lceil\alpha\sqrt{n}\rceil\), after a suitable translation with an integer vector. The algorithm chooses a prime \(p\geq m\) close to \(m\). Recall that _primality testing_ can be realized in polynomial time, that is, in \(O(\log^{O(1)}m)\) time; see, e.g., [22] or [23] (Ch. 14.6). By the Prime Number Theorem, finding a prime \(p\geq m\) close to \(m\) involves the primality testing of \(O(m^{0.525})=O(n^{0.263})\) odd integers in the interval \([m,m+2m^{0.525}]\)[24].  
As argued above, \(G_{m}\) is covered by \(m+p-1\leq(2+\varepsilon)m\)\(m\)-element point sets \(V_{i}\) in general position. By monotonicity (i.e., every subset of a set in general position is likewise in general position), the sets \(P\cap V_{i}\) are in general position, and the algorithm outputs the largest one, with at least \(\frac{n}{(2+\varepsilon)m}\) elements.  
Since each of the \(m\) rows of \(G_{m}\) contains at most two elements of an optimal solution, we have \(\mathsf{OPT}\leq 2m\). Consequently, the ratio \(\mathsf{ALG}/\mathsf{OPT}\) is bounded from below as  
\[\frac{\mathsf{ALG}}{\mathsf{OPT}}\geq\frac{n}{2\cdot(2+\varepsilon)m^{2}}= \Omega\left(\frac{1}{\alpha^{2}}\right).\]  
The approximation ratio in the formula is roughly \(1/(4\alpha^{2})\), for a small \(\varepsilon\). Clearly, the resulting algorithm runs in polynomial time: choosing the prime \(p\) and generating the sets \(V_{i}\) takes \(O(n)\) time. Selecting one \(V_{i}\) with a maximal size \(|P\cap V_{i}|\) can be achieved within the same time, and so the overall running time is \(O(n)\).