ボロノイ分割は必須とまでは言えない

http://q.hatena.ne.jp/1202988234 で、「緯度・経度からだいたいの住所を割り出す計算方法」について質問が出ていました。
街区レベル位置参照情報を使う場合、代表点がずらーっと並んでいるので、指定した点から最も近い代表点を住所として出すというのが、たぶん、基本。
まず考え付くのは、指定した点と代表点との距離を全部出して、その中から最小になる点を得る方法。ただし、O(n^2)のオーダになるので、全国の代表点をしらみつぶしに計算しようとすると、おぞましいことになるのは目に見えています。
ボロノイ分割を使うというのは、サイトに最も近い点で形成される領域を先に作っておくことです。このデータを持っているなら、O(n)のオーダで計算できます。
でも、サイト候補を絞り込めば、その候補についてのみ計算すれば済むので、O(n^2)のオーダとはいえ、現実的な計算時間で計算できると思います。