Подскажите эффективный алгоритм
При таких порядках величин, я бы посоветовал генетические алгоритмы.

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