Spróbowałbym dwóch trików:

1. Podzielić cały obszar na części porównywalne z promieniem r. Wtedy
na szybko można szukać nie wszędzie, ale wśród kilku fragmentów.

1b. Jak wyżej, ale rekursja.

2. Posortować po x i po y. Szukane punkty leżą na przecięciu dwóch
pasów.

Jeszcze jeden pomysł: punkty tworzą siatkę. Najpierw wybieramy jeden
z nich. To powoduje propagację sygnału po siatce. Czyli każdy punkt
wie jakie inne są w pobliżu.