3-Approximation for General position subset

Question

I am currently studying for an exam and stumbled upon the following task: Given the following problem:

Input A set of points $P \subseteq \mathcal{Q}^2$ and $k \in \mathbb{N}$

Question Find the maximum subset $S \subseteq P$ such that no three points in $S$ are collinear.

The task is to find a polynomial time 3-approximation algorithm that is an algorithm that deletes at most $3$-times as many points as an optimal solution. Unfortunately, I am totally clueless here. How would such an algorithm look like?

Answer 1

Find any line containing $\geq 3$ points. Delete all points on this line. Repeat.

This is a $3$-approximation, since on any line containing $m\geq 3$ points we must delete at least $m-2\geq 1$ points and we delete at most $2$ points too many. Meanwhile, the objective value decreases by at least $m-2\geq 1$.

If we know that the true objective value is $K$, then the instance obtained by deleting all points on this line will have objective value $\leq K-(m-2)$ and thus the recursive application will, by induction, return a solution removing at most $3(K-(m-2))$ points. Thus, we remove at most $3(K-(m-2))+m=3K-2m+6\leq 3K$ points.