# Finding those points from a set of points surrounding a specified point most closely

so, I'm working on a piece of code where I want to interpolate a specified point (let's call it target) using only a given set of points. All points from this set can have an intensity between 0% and 100%. So a point at the exact same position will have 100% intensity, points very close to the target will have a intensity between 100% and 0% whereas points far away will have 0% intensity.

My first approach was to specify a radius around the target and a to gradually increase intensity inside this radius depending on the distance. The downside of this approach is, that in a region with a high density of points there will be a high number of points having a non-zero intensity whereas in low density regions there might not be even one point at all having a non-zero itensity.

So now I am looking for an approach where only the 3 (or 4) "closest" points around the target will have an intensity. How do I find a solution to the following problem?

Given a set of points (or vectors) in an arbitrary space (e.g. 2D, 3D, or in my case a sphere surface), I want to find those points which surround a specified point most closely.

e.g.:

• in a 2D space: find the 3 points forming the smallest triangle around the target
• in a 3D space: find the four points forming the smallest tetrahedron
• in my specific case I have a spherical surface or 3D directions and also need to find three points forming a kind of triangle.

As far as I can see, it's not enough to simply select those points with the smallest distance since they could all be positioned in the same direction from the target, thus forming a triangle (or tetrahedron) which does not surround the target.

I am thankful for all ideas and suggestions!

• Probably useful: Voronoi diagram. – ccorn Mar 10 '17 at 9:40
• Thanks! This makes me see it from another perspective: When partitionating the 2D plane in triangles between the points, I want to find out in which triangle the target is inside. The difference to Voronoi diagram from my understanding is, that I don't really care about the centers but about the corners. – John Mar 10 '17 at 10:36