ハッシュマップを使用してポイントが属するエリアを見つける方法を教えてください。

Question

はVoronoi Tessellation経由言う我々は、クラスタに分け、2Dスペースを持って言う：

私たちは、クラスタのアウトライン、ミッドポイントを持っています。そのような空間内のポイント（x、y座標）を与えて、それが所属するクラスターを判別できるようにハッシュを取る方法は？

レイヤーを追加してポイントを所持しているツリーをツリー検索で作成することで、クラスターをバイナリーツリーにすることができます。また私は、各空間点（descreetであると仮定）をクラスタにマッピングし、データのロードを格納するO（1）を取得できることも知っています。しかし、私は、順序付けられていないハッシュマップスタイルを使用して、与えられた点からクラスターを得る方法を模索しています。そのようなことを行う方法（アルゴリズム的に）？

Answer 1

Build kd-tree Voronoiサイト（セル「センタ」）上にあり、O（NlogN）時間内に最も近いサイトを検索します。細胞（おそらく、より複雑な方法）各ボロノイで

Answer 2

のtrapezoid decompositionを構築する」 - ポイントと最も近いサイトの両方が原因ボロノイ図のプロパティ

別のオプションに同じセルに属し

注意クラスタ "は、対応する中間点に最も近い隣接点として有する点の軌跡である。

このように、実際には、新しい点の（すべての中間点の中で）最も近い隣を見つけることに興味があります。

この目的のためにハッシングを使用する場合は、おそらくローカリティセンシティブハッシュについてお読みください。