时间戳

首页 > 解决方案 > 算法：找到仅由它们的分离定义的最小空间跨越点

algorithm - 算法：找到仅由它们的分离定义的最小空间跨越点

问题描述

我在某个 N 维空间中有一组点，我所知道的只是它们之间的距离。假设它是一个无序的结构集合，如下所示：

struct {
    int first;         // Just some identifier that uniquely specifies a point
    int second;        // No importance to which point is first or second
    float separation;  // The distance between the first and second points -- always positive
};

当然，算法不一定是 C 代码。我只是以这种风格编写了结构以使问题清晰。结构破坏了两个端点之间的对称性，这让我很不高兴，但解决这个问题只会让事情变得更加复杂。

假设间隔是由它们之间的毕达哥拉斯距离定义的，并且空间是欧几里得。让我们还指定分离是内部一致的。例如，给定 AB、BC 和 AC 分离，我们知道 AB + BC >= AC。

我想要一个算法来找到可以包含所有点的最小维度空间。在这个算法中，我们可以假设与空间定义的间隔偏差小于某个指定容差的间隔可以忽略不计。

有谁知道这样做的算法？到目前为止，我只能想出非多项式算法。任何人都可以对此进行改进，或者至少做出一些干净且可扩展的东西吗？

为什么这很有趣？在物理学中有一些低层次的理论，例如弦理论或量子环引力，它们并不能明显地预测我们的三维世界。该算法可能是寻找 3d 世界如何出现的项目的一部分。

标签： algorithmmultidimensional-arraygeometrycomputational-geometrymetrics

解决方案

感谢所有在这里发表想法的人。我现在对自己的问题有了答案。这不是很好，因为它执行 O(n^3) 但至少它是多项式的。大致来说，它是这样工作的：

  1. 将问题表示为具有零对角线的对称矩阵 - 表示任意两点之间的距离。这等效于使用结构的表示，但更容易使用。

  2. 假设矩阵隐含的点的顺序（第一列/行=第一点）是合理的。（可能值得寻找更好的顺序，但这是要做的。）

  3. 现在创建一个直角坐标系来拟合这些点，从第一个点开始，我们以 WLOG 作为原点。

  4. 第二点定义 x 轴

  5. 对于每个后续点，我们一次计算一个坐标，从 x 轴开始。我们知道到原点的距离和到点 2 的距离。这允许我们计算 x 坐标，因为我们最终得到两个联立方程 x^2 + y^2 + ... = s1^2 和 (x - x2)^2 + y^2 + ... = s2^2，这使我们可以很容易地根据 x2、点 2 的 x 坐标以及点 1 和 2、s1 和 s2 的距离来计算 x。

  6. 每个新坐标都可以很容易地计算出来，因为到目前为止计算的坐标矩阵是三角形的——每次只有一个未知数。

  7. 每个点的最后一个坐标位于一个新轴上——一个尚未使用的维度。使用毕达哥拉斯计算其与原点的距离的坐标，因为我们知道所有其他坐标。

  8. 新轴上的坐标可能是虚构的——一组通用的距离不能总是用任意维数的坐标系来表示——至少不能用实数表示。如果是这种情况，我会出错。

  9. 对每个新点继续以这种方式进行，为每个点建立一个坐标向量向量。一般来说，这是三角形的，但可能存在我们计算的最终坐标足够接近零的情况，我们认为该点的位置由现有尺寸表示。无论如何我都会存储坐标，但要保持与前一点相同的维度数。我也跳过了这些点，因为计算更多点不需要它们（参见步骤 10）。

  10. 最后，我们已经表示了所有点，使得距离是一致的。

  11. 作为最后的检查，我验证所有点的距离是否匹配，包括在步骤 9 中跳过的点。

  12. 所需的维数是用于最后一点的数字。

如果有人对此（在 Haskell 中）的实现感兴趣，可以在我的 GitHub 页面上https://github.com/MarcusRainbow/EmergentDimensions/coords.hs。

推荐阅读