Listはサイズが大きくなると変更コストも大きくなるので、一定のサイズを超えると変更ではなく再生成のほうが早いです。あとはループを上手く回してGeneratorからListを一気に再生成させれば、Listの変更コスト0かつオーダーNで近接要素を間引くことができます。ループ内の計算コストも高くないので、そんなに時間はかからないと思います。

from operator import __sub__


def filterclose(coordinates, distance):
    a = coordinates[0]
    yield a
    for b in coordinates[1:]:
        if not all(diff < distance for diff in map(abs, map(__sub__, a, b))):
            yield b
            a = b


a_list = [[802, 1593], [802, 1601], [93, 1019], [614, 1019], [1138, 1608], [1128, 1253]]
b_list = list(filterclose(a_list, 40))

print(b_list)  # -> [[802, 1593], [93, 1019], [614, 1019], [1138, 1608], [1128, 1253]]

 追記

複素数使ったりしながら色々試してたら半分以下の時間で完了するようになった。。。

def filterclose(coordinates, distance):
    iterable = iter(coordinates)
    threshold = float(distance)
    a = next(iterable)
    a_comp = complex(*a)
    yield a
    for b in iterable:
        b_comp = complex(*b)
        diff = b_comp - a_comp
        if abs(diff.real) >= threshold or abs(diff.imag) >= threshold:
            yield b
            a, a_comp = b, b_comp

実際のプログラミングにおいて計算オーダーを気にするのは場合によりけりと思います。例えば100個程度しかないデータを処理するのに総当たりを用いて計算量がN^2のオーダーになるからといって、それほど気にする必要もないと思います。10^4程度の計算なんて一瞬で終わるのですから。しかしデータ量が1万とか10万ともなればさすがに多少複雑であっても何か効率のよい方法を考えるべきでしょう。

質問者さんは「データ量が多くても使えるような一般的なアルゴリズム」を考えようとしていますか？それともご自分のアプリケーションに使うための専用の論理を考えようとしていますか？それによりかけるべき手間は変わってくると思います。

それはさておき・・・

総当たりを避ける方法としては例えば探すべき対象は値の大きさで決まるのですからあらかじめ比較対象データをソートしておきバイナリーサーチするといった方法が思いつきます。ある一つの値に近いデータが存在するかどうかの計算量は総当たりではNのオーダーであるのに対して、バイナリーサーチならLog(N)のオーダーとなることが期待できるでしょう。1000個なら総当たりだと平均500回の比較が必要なのに対してバイナリーサーチなら10回程度の比較で近傍の値を見つけられるでしょう。

またバイナリーサーチでもまだ追いつかない場合ハッシュ法のように「あるデータを充分細かいグループに写像し、そのグループの中だけを探す」というアイデアも使えるかも知れません。本件ではある値どうしの一致ではなく「充分近いか」なので、例えば閾値が30なのであれば30程度の距離の違いでも同一のグループになるようなハッシュ関数を考えればそこそこの効率がでそうな気がします。ハッシュ関数を「絶対値を取って30で割る」という方法をベースにすれば、ハッシュ値同士の差が-1, 0, +1のエントリー群のみを比較すればよいことになります。

最初に述べましたがこんな凝ったことをしても100個程度のデータ量だとアルゴリズムの複雑さゆえにかえって遅くなるかも知れません。しかしながらこれが数百万といったオーダーのデータの中から近い値があるかどうかを高速に求めなければならないという状況では有効になるかと思います。

上記はバイナリーサーチやハッシュ法といった計算機プログラミングにおいて非常にポピュラーな方法を述べたに過ぎません。こういう検討は「バイナリーサーチにするとなぜ早いのか」「ハッシュにするとなぜ早いのか」といったアルゴリズムの基本の本質を把握していれば自分でいろいろ工夫することができると思います。逆にアルゴリズムや計算量の本質の方の把握をしていないとこうした検討が難しいと思います。ぜひそういう面でも「各々のアルゴリズムの本質」について少し深く考えてみるとよいのではないでしょうか？

①２つの成分の足します。
②足し合わせたもののソートインデックスを得ます。
③合計値が±60以内のものの集合を作ります。
④それぞれの集合内で比較して条件満たすものを削除します。

削除の要件より緩くて確かめやすい前処理をすることです。

て、1個目の値でソートするだけでnlognですやん。
また無駄なことをしてしまいました。

メモリが無限にあると仮定して、O(N)。

import numpy as np
N = 10**9
M = 10000
th = 30

a = np.random.randint(M, size=(N,2))
def f(a):
    mm = np.max(a, axis=0)+1
    s = np.empty((mm[0], mm[1]), dtype=bool)
    s.fill(1)
    ans = []
    for p in a:
        if s[p[0], p[1]]:
            ans.append(p)
            s[max(0, p[0]-th+1):min(s.shape[0], p[0]+th-1), max(0, p[1]-th+1):min(s.shape[1], p[1]+th-1)] = False
    return np.array(ans)
ans = f(a)