При таких порядках величин, я бы посоветовал генетические алгоритмы.
Уточните, кстати, как примерно соотносится среднее расстояние между двумя ближайшими точками (из множества 10^6) с величиной R. Без этого трудно понять, насколько плотно «заселено» Ваше пространство.
