Given a point set in $\mathbb{R}^2$, I need to find a triangle connecting three points of the set that contains the most points of the set. Points that lie on the connecting lines don't count. The actual area of the triangle doesn't matter to me.
For example, in a $3\times 3$ grid of points spaced evenly from $(0, 0)$ to $(2, 2)$, the triangle in question is any one of $\{(0,0),(2,0),(1,2)\}$ or its four rotations about $(1,1)$, or $\{(1,0),(0,1),(2,2)\}$ or its four rotations, all of which contain one point (viz. $(1,1)$).
I considered brute-forcing or taking some sort of rotating calipers-style approach amongst the points of the convex hull of the point set, but it wasn't clear to me if that approach was even provably valid---the maximum area triangle clearly uses three points in the convex hull, but I couldn't think of a way to reason about the sort of triangles I need.
That approach is provably wrong, as one of the answers shows. How about picking an arbitrary triangle and iteratively replacing each vertex with its closest neighbor not in the triangle, if that replacement increases the number of points in the triangle? Still brute forcey, but better... maybe? I'm also not sure if that's actually correct.
Edit: per the comments, the set of points is finite, and by "a triangle connecting three points of the set" I do mean a triangle whose vertices are points in the set.
Second edit: I would prefer a better-than-brute-horse approach if possible.
Third edit: replaced potential approach
The brute-force approach is $O(n^4)$ where there are $n$ points: enumerate each triangle, and check each point for being inside.