これ、「素直な解答」の方が間違っている。

ぬじゃらだーさんのコメント
このアルゴリズムって点が原点から等距離に分布している場合はまったく働かないですよね。

その通り。その一方で、「近い順にソート」は合っている。しかしこれだとO(n log n)。

TSさんのコメント
もとの最近点探索の問題を解くには、点集合Pのボロノイ図データを作っておいて問い合わせに答えるのが正攻法ではないでしょうか

これだと確かに高速。点がすべて格子点上にある場合(たとえばビットマップ)、ボロノイ図があらかじめ用意してある場合はO(1)で判定できる。たとえば各格子点にあらかじめどの点が一番近いかを記録しておき、それを読むだけでいいので。ただしこれだと格子点の数だけメモリーを使ってしまう上、初期化にえらい時間がかかってしまうので、点集合の各点もまた動いている場合には使いがたい。

moimoiさんのコメント
いや，ボロノイとかデータ点の数が大きくなったときにコスト高すぎますよ．実データだとデータの更新コストがアホみたいにでかくなっちゃいますし

そうやって考えていくと、「とりあえず全ての点までの距離を測る」という素朴なアルゴリズムは、案外バランスが取れているかも知れない。最近点だけでよければ O(n) でもあるし。

というわけで、最近点だけ抽出するデモを。答え合わせのためにソートした結果も表示していますが、時間計測は最近点の検索のみにかけています。これだと10,000点でも10ms台で検索が完了します。ご指摘感謝＞各位

Dan the Distant Man from Perfection

xmax: ymax: #points:
to ( x=, y= ) is ()

Took ms to find

Point = function(x, y){
    this.x = x;
    this.y = y;
};

Point.prototype = {
    dsquare:function(p){
        var dx = this.x - p.x;
        var dy = this.y - p.y;
        return dx*dx + dy*dy;
    },
    distance:function(p){
        return Math.sqrt(this.dsquare(p));
    },
    within:function(p, d){
        return this.dsquare(p) < d * d;
    },
    sorted_by_distance:function(ary){
        var result = ary.slice();
        var self = this;
        result.sort(function(a, b){
            return self.dsquare(a) - self.dsquare(b);
        });
        return result;
    },
    nearest:function(ary){
        var result = ary[0];
        var l = ary.length;
        if (l < 2) return result;
        var md = this.dsquare(ary[0]);
        for (var i = 0; i < l; i++){
            var d = this.dsquare(ary[i]);
            if (d < md){
                result = ary[i];
                md = d;
            }
        }
        return result;
    }
};

randpoints = function(n, xmax, ymax){
    var result = [];
    for (var i = 0; i < n; i++){
        result[i] = new Point(
            Math.floor(Math.random()*xmax), 
            Math.floor(Math.random()*ymax)
        );
    }
    return result;
};

points2str = function(pts){
    var result = [];
    for (var i = 0, l = pts.length; i < l; i++){
        result[i] = '(' + pts[i].x + ', ' + pts[i].y + ')';
    }
    return result.join(', ');
}