0

I am working on an program to compute the structure factor of a given configuration of 3D points, and I need an efficient algorithm to generate all the possible 3D vectors with integer coordinates and magnitude between $n-\delta$ and $n+\delta$, where $\delta$ is "small" compared to $n$.

This is equivalent to finding all the solutions of

$$(n-\delta)^2<\| v \|^2<(n+\delta)^2$$

with $\vec v \in \mathbf{Z}^3$.

Of course I only need to find half the solutions, because the other half will be given by

$$\vec v' = -\vec v$$

What is the best approach to solve this computational problem?

valerio
  • 881
  • Is there a reason why brute force isn't acceptable? It seems that a simple solution would be to traverse the boundary of the cube centered at the origin whose side length is $2\lceil (n+\delta) \rceil$, then subtract 2 from that, etc., repeating until you traverse a cube with no points in the desired annulus. Is it too slow? (I could see why it would be, if $n$ is big and especially if $\delta$ is also fairly big.) – Ian Jun 28 '16 at 13:31
  • Let's see, how many points is that. You check $\lceil n+\delta \rceil - \lfloor n-\delta \rfloor$ boundaries of cubes, in each case the side length is approximately $2n$ (since you say $\delta$ is pretty small). A cube has 12 edges, so that's about $24n$ points to check per "shell" and there are about $2\delta$ shells (or about 2, if $\delta$ is especially small). So is it too hard to directly check about $48n \cdot \max { 1,\delta }$ points? – Ian Jun 28 '16 at 13:58

0 Answers0