Randomized interpolation

[helios]

I wasn't sure whether to put this here or in General. I guess it's more about algorithms than about C++, so here goes:

Suppose you want have a real x and a set of reals S, and you want to match x with one of those numbers. Something simple you can do is find the closest number (the one with the smallest difference with x). This would be nearest neighbor interpolation. Another thing is find the two closest numbers and randomly pick between them based on how close they are. So if abs(x - S[0]) = 1 and abs(x- S[1]) = 10, S[0] should be 10 times more likely to be picked than S[1].

But what do you do if you want to extend that latter algorithm to higher dimensions?

[mbozzi]

If you take a set of points in R^n and perform nearest-neighbor interpolation inside them, you get a Voronoi tessellation.
https://en.wikipedia.org/wiki/Voronoi_diagram

Voronoi diagrams have a connection to mesh construction & point-cloud stuff through triangulation algorithms, in particular the Delaunay triangulation:
https://en.wikipedia.org/wiki/Delaunay_triangulation

I suppose you'd need to randomly interpolate between the nearest cell and the centers of the nearest adjacent Voronoi cells? You can use any distance metric you want.

[helios]

Thanks, that's what I was looking for.