求出以原点为中心、半径为 R、尺寸为 D 的球内整数点的数量

Question

我正在编写一台计算机 program/algorithm 来计算以原点为中心的半径 R 和维度 D 的球体内整数点的数量。本质上，如果我们有一个维度为 2（圆）且半径为 5 的球体，我正在确定不等式 X^2+Y^2 ≤ 25 的所有整数解。不是计算每个可能的整数点，有没有一种有效的方法算点数？使用对称性 ?

Answer 1

好吧，使用对称性，您总是可以只计算正侧的所有整数解，然后反转分量。所以，对于你的 Circle (D=2, R=5)，你只需要找到
{ X,Y ∈ N: X²+Y² ≤ R}。然后创建组合 (X,Y), (X,-Y), (-X,Y), (-X,-Y)
这让您只剩下 (1/2)^D 个解决方案。

此外，您可以将半径为 R 的圆近似为半径为 R/√2 的正方形，因此可以自动添加小于或等于该整数的所有组合。

Answer 2

假设尺寸为3，R为半径。对于 z = 0，可能的 x,y 坐标是半径为 R 的圆内的点，对于任何 z，x,y 是半径为 sqrt( R * R - z * z) 的圆内的点； z 的可能值为 -r, .. 0, 1, .. r，其中 r 是小于 R 的最小整数。请注意 z 和 -z 的计数将相同。

当我们深入到维度 1 时，我们在问有多少个整数 i 满足 |i| < R，这是 1 + 2 * r

所以：

int ncip( int dim, double R)
{   
    int i;
    int r = (int)floor( R);
    if ( dim == 1)
    {   return 1 + 2*r; 
    }
    int n = ncip( dim-1, R); // last coord 0
    for( i=1; i<=r; ++i)
    {   n += 2*ncip( dim-1, sqrt( R*R - i*i)); // last coord +- i
    }
    return n;
}

求出以原点为中心、半径为 R、尺寸为 D 的球内整数点的数量

Finding the number of integer points inside a sphere of radius R and dimension D centered at the Origin

c++

algorithm

geometry

number-theory

computational-geometry