1
$\begingroup$

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

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

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
  • $\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, 2015 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, 2015 at 17:50
0
$\begingroup$

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

$\endgroup$
1
  • $\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, 2015 at 0:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .