Ну да, для данной реализации они вообще говоря каждый раз будут разными. Ну и что? Вон там Vanda в соседней ветке тоже каждый раз картинки разные получает..
Вопрос в том, на сколько это критично? И на сколько критично они "разные" будут в среднем..(Что такое "разные"?)

Тогда отказывайтесь от этого алгоритма. В противном случае, если речь идёт об анимации (много-много картинок) то в этой ситуации картинка неизбежно будет "дрожать".

А вы не ходите вокруг до около..) Я так сразу даже не предложу решения..
Если хотите плавности анимации, то это может оказаться совсем нетривиальная задачка..
Могу пока только сделать предположение, что этот метод должен быть строго детерминистическим и, наверное,
с фиксированной сеткой (без всякого random)

Для инженера - всегда лучше
Ну в конечном счёте и для заказчика.
Но... бабло часто побеждает разум - обычно считается, что "там же только одну функцию починить надо!"

Могу предположить, что это интерполяция (фильтр) между ближайшими кадрами. Т.е. аналог сглаживания одномерной кривой: блур, короче 

Лично меня это интересует с точки зрения/задачи 3D рендера, хотя возможны и др применения за рамками моих интересов. Ну во всяком случае для рендера как-то лазить/считать/иметь 2 кадра одновременно - полная утопия  НО мы можем рендерить один кадр неск раз, и так часто делают для различных "буферных" фич (напр расчет битмаповских теней). Отсюда простая идея немного модифицировать алгоритм стартового поста:

- На первом проходе применяем lazy, но не бежим сразу считать "опорные" точки, а только маркируем/запоминаем их. Эту операцию придется делать в одной нитке, полагаем что она "достаточно быстрая". Заметим что kd-tree здесь не подходит (вставка слишком дорогая)

- После того как опорные точки накоплены, считаем их все наваливаясь всей тушей (нитками), это "разпоточивается" прекрасно.

- И наконец, веселые-счастливые, считаем второй (финальный) проход всеми нитками используя для интерполяции дерево (thread-safe) построенное на первом

Если входные данные следуют в произвольном порядке, то на первом проходе придется снвчала их все сохранить и отсортировать.

Ну это на словах "так просто", на деле тут немало скользких мест, поэтому я бы с удовольствием послушал какие-нить идеи (пусть безумные).

Как всегда, Вы не хотите подумать, даже немного, и спешите "клеить ярлыки" 

Ну ведь вверху подробно разжевано в чем разница между 2 кадрами и 2 проходами (одного и того же кадра). Конечно на каждом новом кадре все начнется с нуля, но если придут те же данные, то и рез-т будет точно тот же.