Multidimensional interpolation

Question

Given a data set in a multidimensional space (in my case, 4D space), where samples are present in all corners of the 4D cube and a significant number of samples in this cube, but not in a neat grid. Each sample has an output value next to it 4D coordinates. The cube has the coordinates [0,0,0,0] .. [1,1,1,1].

Given the new coordinate (4D), how can I get the best interpolated value, given these samples? For example, how to choose samples to begin with, how to interpolate.

As a first guess, I would suggest that this can be done using a two-step process:

• find the smallest convex pentachoron (the 4D equivalent of the three-dimensional tetrahedron / 2D triangle) around the coordinate we need to interpolate.

• interpolate in this tetrahedron.

Especially step 1 seems rather complicated and slow.

Answer 1

Here is the first approach I would try.

Step 1

Find the point of 4 nearest neighbors by Euclidean distance. It is important that these 4 points are linearly independent, since later on they are used to create a barycentric coordinate system. These 4 points become the vertices of your pentachoron (aka 4-simplex).

If the nearest neighbor checks are too slow, try structuring your data in a spatial search tree that works in 4D.

Step 2

Now we need to associate the value with the interpolation point X. Let's start by deriving the X-representation in this new barycentric coordinate system. This barycentric coordinate consists of 4 numbers, which together describe the relative distance between the interpolation point and each of the 4 simplex vertices.

Normalize the barycentric coordinate so that its components sum with 1.

Each of these four simplex vertices is a data point and has an output value. Combine these 4 output values ​​into a vector.

Finally, we interpolate by calculating the point product of the normalized coordinate with the vector of output values.

Source: this idea is actually just a 4D extension of this gem in the middle of the Warypedia Barycentric system system page .