球面上点的均匀分布？

Question

我正在寻找一个算法，以最优方式在球面上分布N个点（不是随机的，我指的是Tammes问题中的最优分布）。 我想用C++实现，但问题不是语言问题，而是算法问题。这是我目前在Python中使用的算法：

# Function to distribute N points on the surface of a sphere 
# (source: http://www.softimageblog.com/archives/115)
def uniform_spherical_distribution(N): 
    pts = []   
    inc = math.pi * (3 - math.sqrt(5)) 
    off = 2 / float(N) 
    for k in range(0, int(N)): 
        y = k * off - 1 + (off / 2) 
        r = math.sqrt(1 - y*y) 
        phi = k * inc 
        pts.append([math.cos(phi)*r, y, math.sin(phi)*r])   
    return pts

对于大量的点来说，视觉效果似乎相当不错，但是对于少量的点（2到10个之间），结果看起来一点也不好（半球中有更多的点）。是否有一种方法可以改进算法，使其在少量的点情况下也能正常工作...（答案可以用C、C++或Python编写）。

- Vincent

---

@Ali OP请求在Tammes问题的意义上进行打包，该问题由提供的链接定义为“在球体表面上打包给定数量的圆，使得圆之间的最小距离最大化”。我建议作为重复帖子的评论由“BlueRaja - Danny Pflughoeft”提供了几乎完全相同的措辞来描述那个帖子正在寻找的内容，然后提供了最高评分的答案来解决这个特定的问题。 - andand

@andand 嗯，我不同意：Vincent要求最优分布，这些答案将给出一些近似分布。请也检查我的答案；我在其他地方找不到这些结果。 - Ali

@Ali，你检查过所有的答案了吗？ - Luka Rahne

@Ali 从我的信息来看，这个问题到目前为止仍然是一个未解决的问题。在2010年，有一个关于5个电子分布最优解的证明。http://arxiv.org/abs/1001.3702。它有66页。 - Luka Rahne

@Ali Paper是来自2001年的http://www-lp.fmf.uni-lj.si/plestenjak/papers.htm。我认为除了这个领域的新突破之外，没有什么更多的可以补充的了。链接问题中的答案有大量高质量的答案和众多链接。 - Luka Rahne

Answer 1

如果你只需要较少数量的点，那么暴力解法或许可以奏效。所谓的暴力解法指的是对于 2 到 10 的解进行预计算并在 N<=10 时进行数组查找。

对于这样小的 N，通过数学优化问题，应该可以实现最佳点分布的求解。你需要多次启动才行，但对于小的 N 这不应该是个问题。下面是我在 AMPL 中的尝试：

param N;

var x{1..N};
var y{1..N};
var z{1..N};

var d;

param xbest{1..N};
param ybest{1..N};
param zbest{1..N};
param dbest;

maximize obj: d;

all_points_on_the_sphere{i in 1..N}:
  x[i]^2 + y[i]^2 + z[i]^2 = 1;

all_pairs{i in 1..N, j in 1..N : i<j}:
  (x[i]-x[j])^2 + (y[i]-y[j])^2 + (z[i]-z[j])^2 >= d;

fix_first_x:  x[1] = 1;
fix_first_y:  y[1] = 0;
fix_first_z:  z[1] = 0;  
fix_second_z: z[2] = 0;

#############################################

option show_stats 1;
option presolve 10;
option substout 1;
option var_bounds 2;
#option nl_comments 0;
#option nl_permute 0;
option display_precision 0;

option solver "/home/ali/ampl/ipopt";

for {k in 2..10} {
    let N := k;  
    solexpand _con;
    let dbest := -1.0;
    # Multistart
    for {1..2000} {
        for {j in 1.._snvars}
            let _svar[j] := Uniform(-1, 1);
        let d := N;     

        solve;

        if (solve_result_num < 200 and d > dbest) then {
            let dbest := d;
            for {i in 1..N} {
                let xbest[i] := x[i];
                let ybest[i] := y[i];
                let zbest[i] := z[i];
            }
        }
    }

    print "@@@";
    printf "N=%d, min distance %6f\n", N, sqrt(dbest);

    for {i in 1..N}
        printf "(%9.6f, %9.6f, %9.6f)\n", xbest[i], ybest[i], zbest[i];
}

在我的机器上运行这个脚本花费了5分钟，解决方案如下：

N=2，最小距离为2.000000 (1.000000，0.000000，0.000000) (-1.000000，0.000000，0.000000)

N=3，最小距离为1.732051 (1.000000，0.000000，0.000000) (-0.500000，0.866025，0.000000) (-0.500000，-0.866025，0.000000)

N=4，最小距离为1.632993 (1.000000，0.000000，0.000000) (-0.333333，-0.942809，0.000000) (-0.333333，0.471405，-0.816497) (-0.333333，0.471405，0.816497)

N=5，最小距离为1.414214 (1.000000，0.000000，0.000000) (-0.208840，0.977950，0.000000) (-0.000000，0.000000，1.000000) (-0.212683，-0.977121，0.000000) (0.000000，0.000000，-1.000000)

N=6，最小距离为1.414214 (1.000000，0.000000，0.000000) (-1.000000，0.000000，0.000000) (0.000000，-0.752754，-0.658302) (0.000000，0.752754，0.658302) (0.000000，0.658302，-0.752754) (0.000000，-0.658302，0.752754)

N=7，最小距离为1.256870 (1.000000，0.000000，0.000000) (-0.688059，-0.725655，0.000000) (0.210138，-0.488836，-0.846689) (0.210138，-0.488836，0.846688) (-0.688059，0.362827，0.628435) (-0.688059，0.362827，-0.628435) (0.210138，0.977672，0.000000)

N=8，最小距离为1.215563 (1.000000，0.000000，0.000000) (0.261204，-0.965284，0.000000) (0.261204，0.565450，0.782329) (-0.783612，-0.482642，-0.391165) (0.261204，-0.199917，-0.944355) (0.261204，0.882475，-0.391165) (-0.783612，0.599750，0.162026) (-0.477592，-0.399834，0.782329)

N=9，最小距离为1.154701 (1.000000，0.000000，0.000000) (-0.500000，-0.866025，0.000000) (0.333333，-0.577350，-0.745356) (-0.500000，0.866025，0.000000) (-0.666667，-0.000000，0.745356) (-0.666667，0.000000，-0.745356) (0.333333，-0.577350，0.745356) (0.333333，0.577350，-0.745356) (0.333333，0.577350，0.745356)

N=10，最小距离为1.091426 (1.000000，0.000000，0.000000) (-0.605995，0.795469，0.000000) (0.404394，0.816443，0.412172) (-0.664045，-0.746251，-0.046407) (0.404394，-0.363508，-0.839242) (-0.664045，0.002497，0.747688) (-0.605995，0.046721，-0.794096) (0.404394，-

通过观察这些数字，很明显有些解决方案可以通过解析计算得出(例如sqrt(2)和sqrt(3))。我相信对于N=2、4和6，解决方案是直线([-1,0,0]，[1,0,0])、四面体和八面体。

上述的点分布可能不是最佳的，没有强烈的保证。非线性求解器可能会陷入局部极值；随着N的增长，局部极值的数量也会增加。

您可以将上述解决方案放在数组中，并在Python、C++或您使用的任何语言中使用它们。

- Ali