# General Position Subset Selection in Line Arrangements +
## 3 Subset Selection in Generic Line Arrangements  
In this section, we prove Theorem 3. Recall that an arrangement of \(n\) lines is generic if it has \(\Omega(n^{2})\) vertices. See Figure 2.  
**Lemma 2**. : _Let \(V\) be the set of vertices of an \(n\) line arrangement \(\mathsf{A}=\mathsf{A}(L)\), where \(L=\{\ell_{1},\ldots,\ell_{n}\}\). Then, \(\ell(V)\leq n-1\)._  
Proof. : We distinguish two cases. Let \(V^{\prime}\subseteq V\) be a set of collinear vertices, say on a line \(h\). If \(h\in L\), then obviously \(|V^{\prime}|\leq n-1\). If \(h\
otin L\), scan \(h\), say, from left to right, and observe that each vertex in \(V^{\prime}\) uses up at least two \"new\" lines from \(L\); thus, \(|V^{\prime}|\leq n/2\). See Figure 3.  
Let \(V\) be the set of vertices of a generic \(n\) line arrangement \(\mathsf{A}=\mathsf{A}(L)\). Let \(N=|V|\leq(\binom{n}{2})\); we also have \(N\geq cn^{2}\) by the assumption. By Lemma 2, \(\ell:=\ell(V)\leq n-1\); thus, by Lemma 1, the number of collinear triples is bounded as  
\[T=O(N^{2}\log\ell+\ell^{2}N)=O(N^{2}\log n+n^{2}N). \tag{2}\]  
Proof of Theorem 3.: The subset selection algorithm consists of two steps: (i) random sampling from \(V\) and (ii) the application of the deletion method. See, e.g., [25] (Chap. 3) and a similar application in [26]. In the first step, a random subset \(X\subset V\) is chosen by selecting points independently with probability \(p=k/N\), for a suitable \(k\) to be determined. Note that \(\mathrm{E}[|X|]=N\cdot k/N=k\). To select a subset in general position, one needs to avoid one type of obstacle, collinear triples. One obstacle can be eliminated by deleting one point from each surviving collinear triple in the second step. In particular, it suffices to choose \(k\) so that  
\[\mathrm{E}[Tp^{3}]\leq k/2,\]  
since this implies that the expected number of remaining points is at least \(k-k/2=k/2\). Let \(c_{1}\) denote the constant hidden in (2). With the previous upper bound on \(T\), and recalling that \(N\geq cn^{2}\), it suffices to choose \(k\) so that  
\[2c_{1}k^{2}(N\log n+n^{2})\leq N^{2}. \tag{3}\]  
Figure 3: Collinear vertices in a line arrangement—incident to an induced dotted line. Figure 2: **Left**: A generic line arrangement consisting of three bundles of \(n/3\) nearly parallel lines each. **Right**: A non-generic line arrangement consisting of \(3\) parallel lines and \(n-3\) concurrent lines. Setting \(k=c^{\prime}\frac{n}{\sqrt{\log n}}\) for a sufficiently small \(c^{\prime}>0\) satisfies the inequality, proving the lower bound on the size of the output. In addition, this setting is valid for ensuring that \(p=k/N<1\). In summary, the expected number of points in general position found using the algorithm is \(\Omega\bigg{(}\frac{n}{\sqrt{\log n}}\bigg{)}\). To analyze the approximation ratio, it suffices to notice that \(\mathsf{OPT}\leq 2n\). Indeed, for each line \(\ell_{i}\in L\), \(i=1,\ldots,n\), at most two vertices in \(V\) can appear in any solution; thus, \(\mathsf{OPT}\leq 2n\). It follows that the approximation ratio is  
\[\frac{\mathsf{ALG}}{\mathsf{OPT}}=\frac{1}{2n}\cdot\Omega\Bigg{(}\frac{n}{ \sqrt{\log n}}\Bigg{)}=\Omega\Bigg{(}\frac{1}{\sqrt{\log n}}\Bigg{)},\]  
as claimed. Since repeated random samplings are independent, the probability of error for the resulting randomized algorithm of not finding the required number of points can be made arbitrarily small by repetition--in standard fashion. Clearly, the resulting algorithm runs in expected polynomial time; we give a few details below. Computing the set of vertices \(V\) and performing the random sampling takes \(O(n^{2})\) time. The expected sample size is \(O(k)=O(n)\). Using the point-line duality, the algorithm computes the line arrangement dual to the point sample in \(O(n^{2})\) time [27] (Ch. 8). It repeatedly removes lines passing through vertices incident to at least three lines, each in \(O(n)\) time, and updates the line arrangement.