# General Position Subset Selection in Line Arrangements +
## 1 Introduction
An \(n\)-element point set \(P\) satisfying the condition \(D(P)\leq\alpha\,n^{1/2}\), for some constant \(\alpha\geq\alpha_{0}\), is said to be _a-dense_; see, for instance, ([PERSON] and [PERSON], 2011) and Figure 1 for an illustration. We obtain a constant-factor approximation for GPSS in dense lattice point sets; its approximation ratio depends on the spread ratio of the input. Figure 1: **Left:** A 2-dense set of \(n=25\) points in the \(8\times 8\) grid (\(m=8\)). **Center:**\(V_{0}\); \(|V_{0}|=m=8\) and \(p=11\); points in \(V_{i}\) may lie outside the grid, e.g., \((3,9)\) lies 2 units above it. **Right**: The approximation algorithm returns \(P\cap V_{0}\) (or \(P\cap V_{3}\)); here, \(|P\cap V_{0}|=|P\cap V_{3}|=4\). **Theorem 2**. : _Given an \(\alpha\)-dense set of \(n\) lattice points, an \(\Omega\big{(}\alpha^{-2}\big{)}\)-approximation for the General Position Subset Selection problem can be computed in polynomial time._  
(II) According to a classical result of [PERSON] [16], if \(P\) is a set of \(n\) points in the plane with at most \(\ell\) points collinear, then \(P\) determines at least \(\Omega\big{(}n(n-\ell)\big{)}\) distinct lines. In particular, if \(\ell\leq cn\), where \(c<1\) is a constant, then \(P\) determines \(\Omega(n^{2})\) distinct lines. By duality (see, e.g., [17]), for a set \(L\) of \(n\) lines in the plane, where at most \(\ell\) lines of \(L\) are concurrent, the number of vertices of the corresponding arrangement is \(\Omega(n(n-\ell))\). We say that an arrangement of \(n\) lines is _generic_ if it has \(\Omega(n^{2})\) vertices. We obtain an \(\Omega((\log n)^{-1/2})\)-approximation for GPSS in the special case where the input set is the set of vertices of an \(n\)-line arrangement under the relatively mild genericity assumption. **Theorem 3**. : _Given \(n\) lines in the plane that make a generic line arrangement, an \(\Omega\Big{(}(\log n)^{-1/2}\Big{)}\)-approximation for the General Position Subset Selection problem for the set of vertices of the corresponding line arrangement can be computed using a randomized algorithm in expected polynomial time._  
Essentially, the same proof (of this theorem in Section 3) yields the following. **Corollary 1**. : _Given \(n\) lines in the plane, let \(V\) denote the vertex set of the corresponding line arrangement. If \(V^{\prime}\subseteq V\) is a subset of vertices with \(|V^{\prime}|=\Omega(n^{2})\), an \(\Omega\Big{(}(\log n)^{-1/2}\Big{)}\)-approximation for the General Position Subset Selection problem in \(V^{\prime}\) can be computed using a randomized algorithm in expected polynomial time._  
It is worth noting that the scenario in Theorem 2 is a special case of the scenario in Theorem 3. Indeed, any finite set \(P\) of lattice points in the integer grid is a subset of the vertices of an arrangement \(\mathsf{A}^{+}\) of axis-parallel lines induced by \(H\) and \(V\), the sets of horizontal and vertical lines incident to points in \(P\), respectively. Moreover, if \(P\) is a dense set, then \(\mathsf{A}^{+}\) is generic, since  
\[|H|_{\cdot}|V|=\Omega(|P|/(\alpha\sqrt{n}))=\Omega(\sqrt{n}),\]  
Thus, \(\mathsf{A}^{+}\) has \(|H|\cdot|V|=\Omega(n)\) vertices. Observe that _not_ all vertices in the arrangement \(\mathsf{A}^{+}\) are necessarily in \(P\). (III) Given a set \(P\) of points in the plane, a _line cover_ of \(P\) is a set of lines that cover all points in \(P\). Computing a line cover of minimum size is \(\mathsf{APX}\)-hard, and the best approximation ratio known is \(O(\log n)\)[18]. We obtain an \(\Omega((\log n)^{-1/2})\)-approximation for GPSS in the special case where the input set has at most \(O(\sqrt{n})\) points collinear and can be covered by \(O(\sqrt{n})\) lines. **Theorem 4**. : _Given a set \(P\) of \(n\) points in the plane with at most \(O(\sqrt{n})\) collinear and with a line cover of size \(O(\sqrt{n})\), an \(\Omega\Big{(}(\log n)^{-1/2}\Big{)}\)-approximation for the General Position Subset Selection problem can be computed using a randomized algorithm in expected polynomial time._