緯度経度から地名を検索する方法。（リバースジオコーディング・リバースジオコーダ）

質問

緯度経度から地名/住所を出力する方法についてのご質問です。

(1)サービス提供者について
緯度経度から地名/住所を出力することをリバースジオコーディングと言うそうですが、そのようなサービス（API提供など）を提供している事業者についてご存知の方はご教授頂けますでしょうか？
※調べた限りですと以下については把握しております
・ReFITS；http://refits.cgk.affrc.go.jp/tsrv/jp/rgeocode.html
・個人；http://www.knya.net/archives/2005/07/rest.html
※GoogleMapsAPIやYahooMapsAPIでも同様のことができるようですが、方法等について詳細を書いてあるサイト等あればご教授下さい。

(2)実現方法（ロジック）について
緯度経度から地名・住所を特定する方法について、ロジック（計算手法等）をご存知の方いらっしゃいましたらご教示頂けますでしょうか？
※各地名の代表地点（緯度経度）と、調べたい地点との距離を計算して、近接する点を検索する方法かな～とか思ってます…。そうなると、計算量が過大になるのではと思いまして。（素人的発想かもしれませんが…）

ざっくりとした質問で恐縮ですが
よろしくお願いいたします。

回答No.1

noocyte

(1) は知りませんが (2) について．

> ※各地名の代表地点（緯度経度）と、調べたい地点との
> 距離を計算して、近接する点を検索する方法かな～とか思ってます…。
> そうなると、計算量が過大になるのではと思いまして。

その検索を効率的に行う方法があります．

幾何学の問題を計算機で効率よく解く方法を研究する学問分野を
「計算幾何学 (Computational Geometry)」といいます．
ご質問の問題は，計算幾何学では「最近点探索 (nearest neighbor search)」
と呼ばれています．これは，ボロノイ図 (Voronoi diagram) を使うと，
検索を高速に行うことができます．

Ｎ個の代表地点があるとすると，検索時間は log(N) 程度で済みます．
なお，予め与えられた代表点についてボロノイ図を作っておく必要がありますが，
それには N * log(N) 程度の時間がかかります．

ボロノイ図とは
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/voronoi-diagram/voronoi-diagram.html

ボロノイ図 (Wikipedia)
http://ja.wikipedia.org/wiki/%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3

大山崇のボロノイ図のページ
(さまざまなボロノイ図を Java で表示できます．Java，VB プログラムのダウンロードも可．)
http://www.nirarebakun.com/voro/voro.html

計算幾何学 (Wikipedia)
http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E5%B9%BE%E4%BD%95%E5%AD%A6

お礼

ありがとうございました。参考になります。