Wenn die Punkte-Liste sortiert ist, dann kannst du doch über eine
binäre Suche ganz schnell den Anfang für deinen Bereich suchen.
Also den ersten Wert, welcher größer-gleich deinem Anfan für das Rechteck ist.
Diese Suche wäre dann mit O(log n) schon recht schnell, so daß bei 1.000.000 Punkten schon nach maximal 20 Vergleichen der Anfang gefunden wäre.