algorithm - 点的均匀分布

Question

我有m一些我希望在n维空间中均匀分布的点。“一致”是指所有最短距离对具有相似的值。

换句话说，我希望这些点尽可能均匀地填充空间。

请问，有谁知道如何做到这一点？这个问题有名字吗？

编辑：

例如，当我有 4 个点和 2D 平面时，坐标应该是 [0, 1], [1, 0], [0, -1], [-1, 0]。只是一个正方形。对于 3D，它是一个立方体。但是如果点数与 2^n 不同，我不确定该怎么办。

另一种思考方式是将点视为相互排斥的带电粒子。但是运行这样的模拟非常慢......

Answer 1

我相信您可能对低差异序列感兴趣。这些被用作 nm 评论中描述的均匀分布的确定性模拟。它们通常用于所谓的“准蒙特卡洛”算法，其中不是随机抽样，而是使用某种或多或少均匀分布在域上的点网格。

这样的点序列不一定满足您给出的“所有最短距离对具有相似值”的条件，但我将此更多地解释为描述的尝试，而不是问题的硬性要求。如果它真的很重要，那么这可能无法解决您的问题。

Answer 2

我认为您可能想研究Sphere Packing。

Answer 3

这是另一个想法（它并不完美，但我不认为这里有任何东西，您可能需要根据您的特定情况的详细信息进行选择）：使用 二进制空间分区（更多信息在这里）。

一般的想法是，您将 n 维空间并使用 (n-1) 维曲面将其分成两部分。然后你拆分这两个新闻空间，依此类推。如果您仔细选择曲面（以便它们分成大致相等的体积并避免有趣的形状，对于某些有趣的定义），那么您可以看到这将是您所要求的近似值。

这种方法的主要优点是它通常非常快（它用于视频游戏和空间模拟）。它不会像低差异序列（听起来很酷）那样快（或均匀），但我想它可以在任意凸包内工作。