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

  • $\begingroup$ I suppose you mean a finite point set, and a triangle whose vertices are in the set. $\endgroup$ – Robert Israel Mar 30 '15 at 23:37
  • $\begingroup$ Precisely, @Robert! Edited the question to reflect those clarifications. $\endgroup$ – rperce Mar 30 '15 at 23:40

This is only an extended comment on one of the approaches proposed by the OP.

The drawing illustrates that focusing only on the extreme points is not valid: a triangle using only red points would miss several points, whereas the triangle using the blue dot misses only two points.

enter image description here

| cite | improve this answer | |
  • $\begingroup$ Stellar counterexample! Unfortunately I haven't any clue on how to do it better than brute-force anymore. I'm not even sure if it is possible to do better than brute force! $\endgroup$ – rperce Mar 31 '15 at 0:58
  • $\begingroup$ Hey, one of my friends and I came up with another potential approach, see if you can come up with a counterexample for that! $\endgroup$ – rperce Mar 31 '15 at 17:50

The brute-force approach is $O(n^4)$ where there are $n$ points: enumerate each triangle, and check each point for being inside.

| cite | improve this answer | |
  • $\begingroup$ You're certainly not wrong, and I'll accept it if nothing else comes along, but perhaps unsurprisingly I was interested in better-than-brute-force solutions. Edited to reflect that. $\endgroup$ – rperce Mar 31 '15 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.