Algorithm to find the closest 3 points that when t

Question

Picture a canvas that has a bunch of points randomly dispersed around it. Now pick one of those points. How would you find the closest 3 points to it such that if you drew a triangle connecting those points it would cover the chosen point?

Clarification: By "closest", I mean minimum sum of distances to the point.

---

This is mostly out of curiosity. I thought it would be a good way to estimate the "value" of a point if it is unknown, but the surrounding points are known. With 3 surrounding points you could extrapolate the value. I haven't heard of a problem like this before, doesn't seem very trivial so I thought it might be a fun exercise, even if it's not the best way to estimate something.

Answer 1

Take the closest N=3 points. Check whether the triange fits. If not, increment N by one and try out all combinations. Do that until something fits or nothing does.

Answer 2

Your problem description is ambiguous. Which triangle are you after in this figure, the red one or the blue one?

The blue triangle is closer based on lexicographic comparison of the distances of the points, while the red triangle is closer based on the sum of the distances of the points.

Edit: you clarified it to make it clear that you want the sum of distances to be minimized (the red triangle).

So, how about this sketch algorithm?

1. Assume that the chosen point is at the origin (makes description of algorithm easy).
2. Sort the points by distance from the origin: P(1) is closest, P(n) is farthest.
3. Start with i = 3, s = ∞.
4. For each triple of points P(a), P(b), P(i) with a < b < i, if the triangle contains the origin, let s = min(s, |P(a)| + |P(b)| + |P(i)|).
5. If s ≤ |P(1)| + |P(2)| + |P(i)|, stop.
6. If i = n, stop.
7. Otherwise, increment i and go back to step 4.

Obviously this is O(n³) in the worst case.

Here's a sketch of another algorithm. Consider all pairs of points (A, B). For a third point to make a triangle containing the origin, it must lie in the grey shaded region in this figure:

By representing the points in polar coordinates (r, θ) and sorting them according to θ, it is straightforward to examine all these points and pick the closest one to the origin.

This is also O(n³) in the worst case, but a sensible order of visiting pairs (A, B) should yield an early exit in many problem instances.

Answer 3

Just a warning on the iterative method. You may find a triangle with 3 "near points" whose "length" is greater than another resulting by adding a more distant point to the set. Sorry, can't post this as a comment.

See Graph.

Red triangle has perimeter near 4 R while the black one has 3 Sqrt[3] -> 5.2 R

Answer 4

This is my first shot:

1. split the space into quadrants with picked point at the [0,0] coords
2. find the closest point from each quadrant (so you have 4 points)
3. any triangle from these points should be small enough (but not necesarilly the smallest)

Answer 5

1. Like @thejh suggests, sort your points by distance from the chosen point.
2. Starting with the first 3 points, look for a triangle covering the chosen point.
3. If no triangle is found, expand you range to include the next closest point, and try all combinations.
4. Once a triangle is found, you don't necessarily have the final answer. However, you have now limited the final set of points to check. The furthest possible point to check would be at a distance equal to the sum of the distances of the first triangle found. Any further than this, and the sum of the distances is guaranteed to exceed the first triangle that was found.
5. Increase your range of points to include the last point whose distance <= the sum of the distances of the first triangle found.
6. Now check all combinations, and the answer is the triangle found from this set with the minimal sum of distances.

Answer 6

second shot

subsolution: (analytic geometry basics, skip if you are familiar with this) finding point of the opposite half-plane

Example: Let's have two points: A=[a,b]=[2,3] and B=[c,d]=[4,1]. Find vector u = A-B = (2-4,3-1) = (-2,2). This vector is parallel to AB line, so is the vector (-1,1). The equation for this line is defined by vector u and point in AB (i.e. A):

X = 2 -1*t
Y = 3 +1*t

Where t is any real number. Get rid of t:

t = 2 - X
Y = 3 + t = 3 + (2 - X) = 5 - X
X + Y - 5 = 0

Any point that fits in this equation is in the line.

Now let's have another point to define the half-plane, i.e. C=[1,1], we get:

X + Y - 5 = 1 + 1 - 5 < 0

Any point with opposite non-equation sign is in another half-plane, which are these points:

X + Y - 5 > 0

solution: finding the minimum triangle that fits the point S

1. Find the closest point P as min(sqrt( (Xp - Xs)^2 + (Yp - Ys)^2 ))
2. Find perpendicular vector to SP as u = (-Yp+Ys,Xp-Xs)
3. Find two closest points A, B from the opposite half-plane to sigma = pP where p = Su (see subsolution), such as A is on the different site of line q = SP (see final part of the subsolution)
4. Now we have triangle ABP that covers S: calculate sum of distances |SP|+|SA|+|SB|
5. Find the second closest point to S and continue from 1. If the sum of distances is smaller than that in previous steps, remember it. Stop if |SP| is greater than the smallest sum of distances or no more points are available.

I hope this diagram makes it clear.