algorithm - 正方形にランダムに分布する n 個の点が与えられたとき、それぞれが占める面積を求めます。

Question

[0,1] × [0,1] にランダムに分布する n 個の点が与えられた場合、その点に最も近い点の面積を各点に割り当てようとします。

より正式には次のとおりです。

[0,1] × [0,1] のn 個の点 (x ₁、x ₂、... x _{n ) が与えられた場合、各 x j}に点の集合 { z | d(z, x _j ) ≤ d(z, x _i ) } (1, 2, .. n) のすべての i に対して。

リモートで効率的なものを思いつくことはできません。何か助けはありますか？

Answer 1

ボロノイ図を生成するためのフォーチュンのアルゴリズムを探しているようです。

Answer 2

http://en.wikipedia.org/wiki/K-d_tree

KDツリーを使用してみてください。