algorithm - 最近点検索

食後のデザートにちょうどよいサイズの問題。

二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです .. - 人力検索はてな

条件は次の通りです

1. 集合Pはあらかじめ、任意の順番でソートしておける
2. 点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる

まずは素直に答えを。

1. 点集合は、あらかじめ原点からの距離順にソートしておく。
2. その集合を、検索したい点の原点からの距離を使って二分探索(binary search)する。

二分探索は exact match でなくてもいいので、この方法でOKです。O(log n)で探索は終わります。

これだけではちょっとつまらないので、点集合を近い順にソートするという問題も考えてみることにします。それが、以下です。

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

Took ms to sort

工夫のしどころとしては、距離そのものではなく距離の二乗をソートキーにしていることがあります。これだと比較的コストの高いMath.sqrt()を使わずに済みます。詳しくは、以下のソースを参照のこと。

この場合でも、点が1000ぐらいでもSafariやFirefoxでは20ms程度でソートが完了しますが、10000になると200msを超えるようになります。

Enjoy!

Dan the JavaScripter

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;
    }
};

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(', ');
}

Comments

このアルゴリズムって点が原点から等距離に分布している場合はまったく働かないですよね。

Posted by ぬじゃらだー at 2009年04月29日 02:29

ですよね．
普通に原点中心に対称に分布してるものに対しても明らかに無駄が多いですし．
食後のデザートとは少し甘く見過ぎでしょうね．
空間インデックスについて少しは調べてから書いたほうがいいんじゃないですか？
工夫のしどころとやらも数値計算，アルゴリズムの知識が少しでもある人なら常識でしょうし．

コンピュータジオメトリの授業の課題として提出されたら，「可」レベルの答えですよ．

Posted by moimoi at 2009年04月29日 03:10

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

http://en.wikipedia.org/wiki/Voronoi_diagram

ボロノイ図を作るO(nlogn)時間アルゴリズム：
http://en.wikipedia.org/wiki/Fortune%27s_algorithm

調べてみるとネット上にあまり日本語の情報がない問題ですね

Posted by TS at 2009年04月29日 03:16

昔、数理工学の授業でこの手の課題が出て、誰一人としてボロノイにいきつかなかったなぁ。。。（遠い目）

Posted by TS at 2009年04月29日 03:33

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

データサイズや分布によって，kd-Tree，R-Tree，SS-Tree，SR-Tree，M-Treeあたりが正攻法かと．
あと，ちょっと変則版として，間違いを許すならLSHなどがインデックス生成，検索ともに高速ですね．

Posted by moimoi at 2009年04月29日 03:40

Nearest neighborは深い問題。例えばLSH(Locality-Sensitive Hashing)については
http://www.mit.edu/~andoni/LSH/

エンジニアリング的手法は実際の状況下で問題を解くのに有効だし、それを考え実装する人は必要ではある。
ただ、こういう影響力のある人には、その奥にあるもっと深遠な世界に言及することも忘れないでほしい。
過剰な期待だろうか。

Posted by at 2009年04月29日 05:08