<p>In general, even telling whether any such point exists is hard; it is equivalent to the <a href="https://en.wikipedia.org/wiki/Lattice_problem#Shortest_vector_problem_(SVP)" rel="nofollow noreferrer">Shortest Vector Problem (SVP)</a>, and it is conjectured that there is no polynomial-time algorithm for this problem.</p>

CC BY-SA 4.0
2018-06-08T22:16:05.637Z
Thank you for your reply @D.W. I am afraid I do not immediately see the connection between the SVP and intersecting the unit ball with the lattice defined over the $\ell_\infty$ unit ball? I am only interested in listing the points that lie inside the sphere, not finding the shortest vector in my lattice.
Deathcrush
CC BY-SA 4.0
2018-06-08T23:19:16.090Z
@Deathcrush, You asked about intersecting a lattice with the $\ell_2$ unit ball.  That's what my question addresses: it's hard to tell whether there exists a point in that intersection (as hard as the SVP).  The $\ell_\infty$ unit ball is irrelevant so I'm not sure why you're bringing that up in your comment.
D.W.
CC BY-SA 4.0
2018-06-09T10:14:49.110Z
Sorry @D.W, I am new to this area and my statements might be imprecise. In my simple case, I am not defining an arbitrary lattice. I am just discretising the $[-1,1]$ interval and using that to create a $d$ dimensional discrete structure (so I generate all possible $d$-vectors with coordinates from the aforementioned interval). In my simple  mind this is like define a "discrete structure" (which I call lattice) over the $d$ dimensional cube of side $2$. Then the question was how to generate the points that lie inside the sphere without explicitly generating all those in the cube...
Deathcrush
CC BY-SA 4.0
2018-06-09T15:04:32.457Z
@Deathcrush, please edit the question to clarify what you mean, then.
D.W.
CC BY-SA 4.0
2018-06-09T17:13:18.267Z
@Deathcrush why not consider your lattice as a graph in the natural way and run BFS on it?
Sasho Nikolov
CC BY-SA 4.0
2018-06-10T00:34:45.763Z
The clarified version of the problem is not research-level and therefore is off-topic here.
David Eppstein
CC BY-SA 4.0
2018-06-11T08:16:56.580Z
@ D.W. I will edit the question.
Deathcrush
CC BY-SA 4.0
2018-06-11T08:17:24.660Z
@ Sasho: I will think about this approach! Thanks for the suggestion!
Deathcrush
CC BY-SA 4.0
2018-06-08T19:40:34.787Z
2018-06-08T19:40:34.787Z
D.W.
<p>I am interested to know if there is a standard algorithm for generating all the lattice points inside the $d$-dimensional unit ball (with respect to the $\ell_2$-norm).</p>

<p>The brute force approach is to generate the lattice over the $\ell_\infty$ unit ball and then loop through each of the points and remove those with norm strictly greater than $1$. I was wondering if there is a more elegant approach to solving this problem. My initial thoughts are to attempt to cover the $d-1$ dimensional sphere with $n$ points and try and use those points to find out the "limits" that I can then use to generate the lattice coordinate vectors. Then I would define the lattice over the intervals defined by these limits $[a_1,b_1] \times [a_2,b_2] \times … \times [a_d,b_d]$. However, in my mind it is non-trivial to decide how many points to put on the sphere and the algorithm for actually determining the aforementioned limits.</p>

<p>Another approach would be to think of what are the coordinates of the maximum volume polyhedron that can be inscribed in the ball and then somehow constrain them to be on the lattice...Again, this seems to be non trivial. A similar line of thought would be to find the minimum volume polyhedron in which we can include the unit ball by enforcing the constraint that its vertices are lattice points. Then we can just subtract the distance between two lattice points and end up inside the sphere...</p>

<p>Are any of these problems with known solutions/non-trivial to solve?</p>

<p>Thank you in advance.</p>

CC BY-SA 4.0
2018-06-08T19:51:44.033Z
It's non-trivial to "generate the lattice over the $\ell_\infty$ unit ball and then loop through each of the points." If you're given a bad enough basis, you may have to consider arbitrarily large integer combinations of basis vectors before finding the shortest one.
Huck Bennett
CC BY-SA 4.0
2018-06-08T22:36:29.490Z
@Huck Bennett: Thank you for your reply. I am not sure how my question relates to the SVP (pardon my ignorance, I come from a different field)? I am looking to list all the points on the lattice inside the unit ball. To simplify the problem, I have decided to choose a discretisation of the $[−1,1]$ interval (with say k=4 points in total) and construct all the $k^d$
possible coordinate points. Then one can remove those points that have norm greater than $1$. Any pointers to relevant work in the field would be appreciated!
Deathcrush
CC BY-SA 4.0
2018-06-09T04:27:42.280Z
@Deathcrush what do you mean by "the lattice"? What lattice? How is it specified? I feel like you mean some scaling of the integer lattice, i.e. $t \mathbb{Z}^n$ for some $t \in \mathbb{R}$. Is that the case? Or do you mean an arbitrary lattice specified by a basis https://en.wikipedia.org/wiki/Lattice_(group)?
Sasho Nikolov
<lattice><high-dimensional-geometry>
Lattice generation inside d-dimensional unit ball
Deathcrush
# Lattice generation inside d-dimensional unit ball

(Asked by: username_0 on 2018-06-08)

I am interested to know if there is a standard algorithm for generating all the lattice points inside the $d$-dimensional unit ball (with respect to the $\ell\_2$-norm).

The brute force approach is to generate the lattice over the $\ell\_\infty$ unit ball and then loop through each of the points and remove those with norm strictly greater than $1$. I was wondering if there is a more elegant approach to solving this problem. My initial thoughts are to attempt to cover the $d-1$ dimensional sphere with $n$ points and try and use those points to find out the "limits" that I can then use to generate the lattice coordinate vectors. Then I would define the lattice over the intervals defined by these limits $[a\_1,b\_1] \times [a\_2,b\_2] \times … \times [a\_d,b\_d]$. However, in my mind it is non-trivial to decide how many points to put on the sphere and the algorithm for actually determining the aforementioned limits.

Another approach would be to think of what are the coordinates of the maximum volume polyhedron that can be inscribed in the ball and then somehow constrain them to be on the lattice...Again, this seems to be non trivial. A similar line of thought would be to find the minimum volume polyhedron in which we can include the unit ball by enforcing the constraint that its vertices are lattice points. Then we can just subtract the distance between two lattice points and end up inside the sphere...

Are any of these problems with known solutions/non-trivial to solve?

Thank you in advance.

**Tags:** lattice, high-dimensional-geometry

> **Comments:**
> **username_1**: It's non-trivial to "generate the lattice over the $\ell_\infty$ unit ball and then loop through each of the points." If you're given a bad enough basis, you may have to consider arbitrarily large integer combinations of basis vectors before finding the shortest one.  
> **username_0**: @username_1: Thank you for your reply. I am not sure how my question relates to the SVP (pardon my ignorance, I come from a different field)? I am looking to list all the points on the lattice inside the unit ball. To simplify the problem, I have decided to choose a discretisation of the $[−1,1]$ interval (with say k=4 points in total) and construct all the $k^d$ possible coordinate points. Then one can remove those points that have norm greater than $1$. Any pointers to relevant work in the field would be appreciated!  
> **username_2**: @username_0 what do you mean by "the lattice"? What lattice? How is it specified? I feel like you mean some scaling of the integer lattice, i.e. $t \mathbb{Z}^n$ for some $t \in \mathbb{R}$. Is that the case? Or do you mean an arbitrary lattice specified by a basis https://en.wikipedia.org/wiki/Lattice_(group)?  

---

## 1 answers

### Answer by username_3 on 2018-06-08. Score: 1

In general, even telling whether any such point exists is hard; it is equivalent to the [Shortest Vector Problem (SVP)](https://en.wikipedia.org/wiki/Lattice_problem#Shortest_vector_problem_(SVP)), and it is conjectured that there is no polynomial-time algorithm for this problem.

> **Comments:**
> **username_0**: Thank you for your reply @username_3 I am afraid I do not immediately see the connection between the SVP and intersecting the unit ball with the lattice defined over the $\ell_\infty$ unit ball? I am only interested in listing the points that lie inside the sphere, not finding the shortest vector in my lattice.  
> **username_3**: @username_0, You asked about intersecting a lattice with the $\ell_2$ unit ball.  That's what my question addresses: it's hard to tell whether there exists a point in that intersection (as hard as the SVP).  The $\ell_\infty$ unit ball is irrelevant so I'm not sure why you're bringing that up in your comment.  
> **username_0**: Sorry @D.W, I am new to this area and my statements might be imprecise. In my simple case, I am not defining an arbitrary lattice. I am just discretising the $[-1,1]$ interval and using that to create a $d$ dimensional discrete structure (so I generate all possible $d$-vectors with coordinates from the aforementioned interval). In my simple  mind this is like define a "discrete structure" (which I call lattice) over the $d$ dimensional cube of side $2$. Then the question was how to generate the points that lie inside the sphere without explicitly generating all those in the cube...  
> **username_3**: @username_0, please edit the question to clarify what you mean, then.  
> **username_2**: @username_0 why not consider your lattice as a graph in the natural way and run BFS on it?  
> **username_4**: The clarified version of the problem is not research-level and therefore is off-topic here.  
> **username_0**: @ username_3 I will edit the question.  
> **username_0**: @ Sasho: I will think about this approach! Thanks for the suggestion!  

---

