[try Beta version]
Not logged in

 
 
Randomized interpolation

Mar 16, 2020 at 11:37pm
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?
Mar 17, 2020 at 2:04am
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.
Last edited on Mar 17, 2020 at 2:06am
Mar 17, 2020 at 2:27am
Thanks, that's what I was looking for.
Topic archived. No new replies allowed.