Path: coconuts.jaist!wnoc-tyo-news!news.nc.u-tokyo.ac.jp!makino
From: makino@chianti.c.u-tokyo.ac.jp (Jun Makino)
Newsgroups: fj.lang.c,fj.comp.theory,fj.comp.image
Subject: Re: Algorithm searching for nearest point
Date: 15 Feb 1997 08:21:14 GMT
Organization: College of Arts and Sciences, Univ. of Tokyo
Lines: 25
Message-ID: <MAKINO.97Feb15172114@muscat.c.u-tokyo.ac.jp>
References: <1997Feb13.181031.13426@tsn.or.jp>
	<KAZM.97Feb14191437@mickey.kazm.ca2.so-net.or.jp>
NNTP-Posting-Host: muscat.c.u-tokyo.ac.jp
In-reply-to: kazm@kazm.ca2.so-net.or.jp's message of 14 Feb 1997 10:14:37 GMT
Xref: coconuts.jaist fj.lang.c:4468 fj.comp.theory:597 fj.comp.image:2582

>>>>> On 14 Feb 1997 10:14:37 GMT, kazm@kazm.ca2.so-net.or.jp
(Kazuyuki Matsuda) said:

>>>>> "SONE" == SONE Takeshi <ts1@tsn.or.jp> writes:
SONE> 空間上の点(座標)の集合があるとします。
SONE> この集合から、ある任意の点に最も近い点を検索するには、
SONE> どのようなアルゴリズムやデータ構造があるでしょうか?

> あまり詳しいわけではないんですが、Voronoi 図を使う方法があり
> ます。もともとは２次元上での探索ですが、３次元空間にも応用で
> きるはずです。

> 最初に与えられた点の集合から隣り合う２点の中点の集合(直線に
> なる)を求めると、亀の甲のような図形ができあがります。これを
> 予め作っておくと、求める点がどの甲の部分にあるかを判定するだ
> けで最近点がわかります。

作っておけばわかるというのはそうなんですが、作るのは結構コストが
かかりませんか？

点の分布が一様に近いのならグリッドに切って自分のいるところと隣接
セル（なければ見つかるまでその先を、、、）探すとか、一様でなけれ
ば oct-tree を使うとかならやったことがありますが、、、

牧野＠東大駒場