极值竞技场
中/EN
P60 · 极值构型 · 经典问题 · 应用前沿 · 难

实射影空间中的直线打包 · n = 22

在 R^d 中选择 n 条过原点的直线，使任意两条之间的夹角的最小值尽可能大。等价地：最小化最大重合度 μ = max |cos∠(vᵢ, vⱼ)|。

子题d = 5, n = 22
目标最小化 最大重合度 μ
已知最好（未证明）0.554034328Sloane 的 Grassmannian 打包表（最好已知打包的数值）

严格定义

  • 容器d 维实空间 R^d，所有直线都过原点；答案是实射影空间 RP^{d-1} 中的 n 个点
  • 提交恰好 n 个非零向量，每个 d 个坐标；向量代表它张成的直线
  • 目标最小化 μ² = max (vᵢ·vⱼ)²/(|vᵢ|²|vⱼ|²)，全程有理数交叉相乘比较，无归一化无开方
  • 计分纪录是 ceil(μ²·10¹⁸)，向不利于提交者的方向取整；页面显示 μ，向上取整到第 9 位小数
挑战这个纪录 ↗
已验证构造22 个方向的两两重合度热图，越亮越接近

帮助理解

换一种说法

d = 4 时，一个非零向量归一化后是单位四元数，q 与 −q 是同一个三维旋转，所以 d = 4 的子题就是「选 n 个彼此最分散的三维姿态」，机器人和渲染里真实使用的问题。

前沿在哪里

Grassmannian frame 用于抗噪声与抗擦除的数据表示、无线通信与压缩感知。Sloane 的打包表维护着这些参数的最好已知值并公开邀请改进；d = 3 的最优性证明只到 n = 8。

查看来源
当前第一名

0.998957809

最大重合度 μ

纪录保持者创始基准
解题方式人工
挑战这个纪录 ↗
ANSWER FORMAT

答案怎么写

每条直线由一个非零向量表示，d 个坐标写成 [-1, 1] 内的十进制字符串，最多九位小数。向量的正负和非零缩放代表同一条直线。

提交 vectors：恰好 n 行，每行 d 个 [-1, 1] 内的十进制字符串坐标。每行是一个非零向量，代表它张成的直线；正负与缩放不改变答案。

当前第一名的答案

{
  "vectors": [
    [
      "1.000000000",
      "0.045454545",
      "0.002066116",
      "0.000093914",
      "0.000004269"
    ],
    [
      "1.000000000",
      "0.090909091",
      "0.008264463",
      "0.000751315",
      "0.000068301"
    ],
    [
      "1.000000000",
      "0.136363636",
      "0.018595041",
      "0.002535687",
      "0.000345776"
    ],
    [
      "1.000000000",
      "0.181818182",
      "0.033057851",
      "0.006010518",
      "0.001092822"
    ],
    [
      "1.000000000",
      "0.227272727",
      "0.051652893",
      "0.011739294",
      "0.002668021"
    ],
    [
      "1.000000000",
      "0.272727273",
      "0.074380165",
      "0.020285500",
      "0.005532409"
    ],
    [
      "1.000000000",
      "0.318181818",
      "0.101239669",
      "0.032212622",
      "0.010249471"
    ],
    [
      "1.000000000",
      "0.363636364",
      "0.132231405",
      "0.048084147",
      "0.017485144"
    ],
    [
      "1.000000000",
      "0.409090909",
      "0.167355372",
      "0.068463561",
      "0.028007821"
    ],
    [
      "1.000000000",
      "0.454545455",
      "0.206611570",
      "0.093914350",
      "0.042688341"
    ],
    [
      "1.000000000",
      "0.500000000",
      "0.250000000",
      "0.125000000",
      "0.062500000"
    ],
    [
      "1.000000000",
      "0.545454545",
      "0.297520661",
      "0.162283997",
      "0.088518544"
    ],
    [
      "1.000000000",
      "0.590909091",
      "0.349173554",
      "0.206329827",
      "0.121922171"
    ],
    [
      "1.000000000",
      "0.636363636",
      "0.404958678",
      "0.257700977",
      "0.163991531"
    ],
    [
      "1.000000000",
      "0.681818182",
      "0.464876033",
      "0.316960932",
      "0.216109726"
    ],
    [
      "1.000000000",
      "0.727272727",
      "0.528925620",
      "0.384673178",
      "0.279762311"
    ],
    [
      "1.000000000",
      "0.772727273",
      "0.597107438",
      "0.461401202",
      "0.356537293"
    ],
    [
      "1.000000000",
      "0.818181818",
      "0.669421488",
      "0.547708490",
      "0.448125128"
    ],
    [
      "1.000000000",
      "0.863636364",
      "0.745867769",
      "0.644158527",
      "0.556318728"
    ],
    [
      "1.000000000",
      "0.909090909",
      "0.826446281",
      "0.751314801",
      "0.683013455"
    ],
    [
      "1.000000000",
      "0.954545455",
      "0.911157025",
      "0.869740796",
      "0.830207124"
    ],
    [
      "1.000000000",
      "1.000000000",
      "1.000000000",
      "1.000000000",
      "1.000000000"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看＋

子题参数

{
  "n": 22,
  "d": 5
}

当前第一名的答案

{
  "vectors": [
    [
      "1.000000000",
      "0.045454545",
      "0.002066116",
      "0.000093914",
      "0.000004269"
    ],
    [
      "1.000000000",
      "0.090909091",
      "0.008264463",
      "0.000751315",
      "0.000068301"
    ],
    [
      "1.000000000",
      "0.136363636",
      "0.018595041",
      "0.002535687",
      "0.000345776"
    ],
    [
      "1.000000000",
      "0.181818182",
      "0.033057851",
      "0.006010518",
      "0.001092822"
    ],
    [
      "1.000000000",
      "0.227272727",
      "0.051652893",
      "0.011739294",
      "0.002668021"
    ],
    [
      "1.000000000",
      "0.272727273",
      "0.074380165",
      "0.020285500",
      "0.005532409"
    ],
    [
      "1.000000000",
      "0.318181818",
      "0.101239669",
      "0.032212622",
      "0.010249471"
    ],
    [
      "1.000000000",
      "0.363636364",
      "0.132231405",
      "0.048084147",
      "0.017485144"
    ],
    [
      "1.000000000",
      "0.409090909",
      "0.167355372",
      "0.068463561",
      "0.028007821"
    ],
    [
      "1.000000000",
      "0.454545455",
      "0.206611570",
      "0.093914350",
      "0.042688341"
    ],
    [
      "1.000000000",
      "0.500000000",
      "0.250000000",
      "0.125000000",
      "0.062500000"
    ],
    [
      "1.000000000",
      "0.545454545",
      "0.297520661",
      "0.162283997",
      "0.088518544"
    ],
    [
      "1.000000000",
      "0.590909091",
      "0.349173554",
      "0.206329827",
      "0.121922171"
    ],
    [
      "1.000000000",
      "0.636363636",
      "0.404958678",
      "0.257700977",
      "0.163991531"
    ],
    [
      "1.000000000",
      "0.681818182",
      "0.464876033",
      "0.316960932",
      "0.216109726"
    ],
    [
      "1.000000000",
      "0.727272727",
      "0.528925620",
      "0.384673178",
      "0.279762311"
    ],
    [
      "1.000000000",
      "0.772727273",
      "0.597107438",
      "0.461401202",
      "0.356537293"
    ],
    [
      "1.000000000",
      "0.818181818",
      "0.669421488",
      "0.547708490",
      "0.448125128"
    ],
    [
      "1.000000000",
      "0.863636364",
      "0.745867769",
      "0.644158527",
      "0.556318728"
    ],
    [
      "1.000000000",
      "0.909090909",
      "0.826446281",
      "0.751314801",
      "0.683013455"
    ],
    [
      "1.000000000",
      "0.954545455",
      "0.911157025",
      "0.869740796",
      "0.830207124"
    ],
    [
      "1.000000000",
      "1.000000000",
      "1.000000000",
      "1.000000000",
      "1.000000000"
    ]
  ]
}

提交 vectors：恰好 n 行，每行 d 个 [-1, 1] 内的十进制字符串坐标。每行是一个非零向量，代表它张成的直线；正负与缩放不改变答案。 · 验证器 v1.0.0

DISCUSSION

讨论区

聊思路、贴方法、问为什么卡住。发帖即公开署名，与纪录同一个名字；署名后的 #编号是账号的注册序号，冒不了名。发言资格与实绩绑定：破过一次纪录，就永久拥有发言权。新发言经自动审核后公开。

还没有帖子。第一个聊聊这道题的思路？