求仅已知两两间距的点集所需最小欧氏空间维度的算法

你要的多项式时间复杂度方案可以用**经典多维缩放（Classical Multidimensional Scaling, 经典MDS）**实现，时间复杂度为O(n³)（n为点的总数），实现逻辑简洁且易扩展容差规则，具体步骤如下：

步骤1：生成距离矩阵 #

首先把你输入的无序距离对转换为n×n的对称距离矩阵D，其中D[i][j]表示编号为i、j的两个点的距离，对角线元素D[i][i] = 0。
你给出的C风格结构体数据可以直接遍历填充：

// 示例逻辑，不限语言实现
for each entry in distance_set:
    i = entry.first
    j = entry.second
    D[i][j] = entry.separation
    D[j][i] = entry.separation

步骤2：构造中心化内积矩阵 #

经典MDS的核心是通过距离矩阵反演点的内积结构：

1. 构造n阶中心化矩阵 H = I - (1/n) * 1*1^T，其中I是单位矩阵，1是所有元素为1的n维列向量
2. 对距离矩阵的每个元素取平方得到D_sq，即D_sq[i][j] = D[i][j] * D[i][j]
3. 计算内积矩阵 B = -0.5 * H * D_sq * H
   由于输入距离是欧氏距离且自洽，B一定是半正定实对称矩阵。

步骤3：特征值分解求最小维度 #

对B做特征值分解，将得到的特征值按从大到小排序为λ₁ ≥ λ₂ ≥ ... ≥ λₙ ≥ 0，最小嵌入维度k的计算规则和你要求的容差完全适配：

• 设置容差阈值ε（支持绝对误差阈值或方差解释率阈值）
• 若使用绝对误差：k为满足λₖ ≥ ε的最大序号，所有小于ε的特征值视为数值误差直接忽略
• 若使用方差解释率：k为满足(λ₁+λ₂+...+λₖ)/(λ₁+λ₂+...+λₙ) ≥ 1-ε的最小序号，可保证重构距离和原始距离的偏差在可控范围内
  如果需要得到所有点在k维空间的具体坐标，直接取前k个特征值对应的特征向量矩阵V，以及对角矩阵Λ = diag(√λ₁, √λ₂, ..., √λₖ)，坐标矩阵X = V * Λ即可。

方案优势 #

• 时间复杂度远低于非多项式算法，n在1000量级时普通PC即可秒出结果
• 容差规则可灵活配置，支持绝对误差、相对误差两种阈值设定
• 生态支持完善，Python、Julia、R等语言都有成熟的开箱实现，自定义开发也只需要调用成熟线性代数库的特征值分解接口
• 完全适配你的研究场景：如果计算得到的k稳定为3，即可验证底层规则涌现三维空间的假设，也可调整容差观测维度的变化趋势。
  如果遇到输入距离对不完整的场景，只需要改用加权MDS或者ISOMAP算法，先通过最短路径补全缺失距离即可，扩展成本极低。

内容的提问来源于stack exchange，提问作者collideorscape