algorithm - 给定n个随机分布在正方形中的点，求每个点占据的面积

Question

给定 n 个随机分布在 [0,1] × [0,1] 中的点，我尝试将最接近该点的点的面积分配给每个点。

更正式如下：

给定[0,1] × [0,1] 中的n 个点 (x ₁ , x ₂ , ... x _{n )，为每个 x j}分配一个值，该值等于点集 { z | 对于 (1, 2, .. n) 中的所有 i， d(z, x _j ) ≤ d(z, x _i ) }。

我想不出任何远程有效的东西。有什么帮助吗？

Answer 1

听起来您正在寻找Fortune生成Voronoi 图的算法。

Answer 2

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

您可能想尝试使用 KD 树。