Такая штука. У меня на плоскости (две координаты) есть огромное число движущихся точек (нереально много, скажем миллиард). Все эти точки у меня в списке. Точки эти взаимодействуют, если они - геометрические соседи, отстоят друг от друга на небольшое дельта > 0.
Понятно, что на каждом шаге по времени можно пройтись по этому списку точек и определить соседей и провзаимодействовать их. Но это очень стремно O(n^2). На выручку приходит параллельная merge сортировка и все становится O(n*log(n)). Но я не достаточно счастлив со своими решениями. Первое принадлежит не мне и состоит в разбиении плоскости на клетки и ведении учета какая точка в какой клетке. Мое решение - три списка иметь по каждой координате и на каждом шаге по времени их сортировать. В итоге соседи будут соседями во всех трех списках.
Уверен, что-то есть стандартное или кто-то уже это делал. Предложите подход, пожалуйста.
