<p>It's probablyly much easier than factoring $n$, because you're looking for smooth numbers smaller than $n$ rather than for difficult factorizations; a smooth number is one that has many small factors, and these are the distances which will give you the most points on the lattice. If the center has to be at $(0,0)$, then you calculate how many lattice points are at distance $5^{a/2}13^{b/2}17^{c/2}29^{d/2}37^{e/2} \ldots$ using <a href="http://mathworld.wolfram.com/SumofSquaresFunction.html">the formula</a> for the number of ways of expressing a number as the sum of two squares. You can do the same thing for the circle centered at $(0,\frac{1}{2})$ or $(\frac{1}{2},\frac{1}{2})$. You can then do an optimization to find the largest value where this distance is less than $n/2$. I expect that this will be possible in polynomial time using dynamic programming.</p>

<p>I cannot imagine that the largest value would not correspond to the center having coordinates other than $0$ or $\frac{1}{2}$, but this should be proved.  </p>

CC BY-SA 3.0
2011-11-28T22:03:14.913Z
thanks for your quick answer! Experimentally, the optimal circles were always centered around either 0 or 1/2. Any hints about how would one prove this?
Ramzi
CC BY-SA 3.0
2011-11-29T03:00:46.413Z
I don't know how one would prove this; I don't even know if it's true. It is true that the largest exponent on a prime required is order $\log \log n$, which means that exhaustive search can find the optimum answer in pseudopolynomial time $\log^{(\log\log n)} n$, which is still a lot better than factoring. I thought this could be sped up to polynomial time by dynamic programming, but I'm not sure that's right.
Peter Shor 
CC BY-SA 3.0
2011-11-30T01:19:50.883Z
Addendum to previous note: a clever exhaustive search algorithm can find the optimum answer in time $(\log n)^{O(\log\log\log n)}$.
Peter Shor 
CC BY-SA 3.0
2011-11-30T03:52:45.240Z
Thanks again Peter! I wonder if an exhaustive search is unavoidable for this problem. At this point, the problem is close enough to P but not there yet :-) I will try to look for a randomized solution.
Ramzi
CC BY-SA 3.0
2011-11-30T03:53:59.417Z
I still don't know how to show the optimal circle is centered around 0 or 1/2, either.
Peter Shor 
CC BY-SA 3.0
2011-11-30T16:03:38.503Z
It's actually not true that the optimal circles are centered around points with coordinates 0 or +/-1/2. Sorry for my first comment (my simulation results show other points too).
Ramzi
CC BY-SA 3.0
2011-11-30T16:34:41.183Z
@Ramzi: interesting. What kind of points are they centered around?
Peter Shor 
CC BY-SA 3.0
2011-12-01T05:24:08.257Z
for a given $n$, there are often many optimal circles, some of which are not centered around a point in $\{-1/2,0,1/2\}\times\{-1/2,0,1/2\}$ . But it is true (of course according to simulations) that among those optimal circles, there are always some centered around elements of $\{-1/2,0,1/2\}\times\{-1/2,0,1/2\}$. For instance, for $n=5$, optimal circles contain $4$ lattice points, and the circle of center $(0,1)$ and radius $1$ is one of them. For $n=9$, the circle of center $(3/2,3/2)$ and radius $5/2$ is also optimal (contains $8$ lattice points).
Ramzi
CC BY-SA 3.0
2011-12-01T05:25:09.737Z
BTW, for both examples, the point in the middle of the grid is the origin $(0,0)$. I also noticed that whenever a solution is unique, the center of the optimal circle always belong to $\{-1/2,0,1/2\}\times\{-1/2,0,1/2\}$.
Ramzi
CC BY-SA 3.0
2011-12-01T05:34:38.407Z
Hi Ramzi: I didn't make myself clear; what I meant to say was that the center of all optimal circles would be at integer or half-integer coordinates, not 0 and 1/2, despite that being what I said. Sorry.
Peter Shor 
CC BY-SA 3.0
2011-12-01T15:07:13.433Z
Thanks for the clarification Peter! At this point, what you've conjectured seems to be consistent with my simulation results.
Ramzi
CC BY-SA 3.0
2011-12-07T14:01:25.087Z
I think the following properties seem to hold: (1) The number of lattice points in an optimal circle is a multiple of 4, (2) The radius squared of an optimal circle is either an integer or half integer, and (3) There's always an optimal circle centered around (0,0) or (1/2,0) or (1/2, 1/2).
Ramzi
CC BY-SA 3.0
2011-11-28T19:20:33.890Z
2011-11-28T21:40:49.100Z
2011-11-28T21:40:49.100Z
Peter Shor 
<p>You're given an $n\times n$ lattice $\mathcal{L}$, and you're asked to compute the maximum number of points in $\mathcal{L}$ that can belong to the same circle (the circle has to be enclosed by the outer sides of $\mathcal{L}$ and its center does not need to be in $\mathcal{L}$). How hard is this problem? Is it harder than factoring $n$? Are there decent bounds or estimates on the max number defined above?</p>

CC BY-SA 3.0
2011-11-28T19:02:47.903Z
This is somehow related to http://cstheory.stackexchange.com/questions/8406/computing-integer-points-on-the-circumference-of-a-given-circle
Ramzi
<cc.complexity-theory><np-hardness>
Hardness of computing circles with max number of lattice points
Ramzi
# Hardness of computing circles with max number of lattice points

(Asked by: username_0 on 2011-11-28)

You're given an $n\times n$ lattice $\mathcal{L}$, and you're asked to compute the maximum number of points in $\mathcal{L}$ that can belong to the same circle (the circle has to be enclosed by the outer sides of $\mathcal{L}$ and its center does not need to be in $\mathcal{L}$). How hard is this problem? Is it harder than factoring $n$? Are there decent bounds or estimates on the max number defined above?

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_0**: This is somehow related to http://cstheory.stackexchange.com/questions/8406/computing-integer-points-on-the-circumference-of-a-given-circle  

---

## 1 answers

### Answer by username_1 on 2011-11-28. Score: 6 | Accepted answer

It's probablyly much easier than factoring $n$, because you're looking for smooth numbers smaller than $n$ rather than for difficult factorizations; a smooth number is one that has many small factors, and these are the distances which will give you the most points on the lattice. If the center has to be at $(0,0)$, then you calculate how many lattice points are at distance $5^{a/2}13^{b/2}17^{c/2}29^{d/2}37^{e/2} \ldots$ using [the formula](http://mathworld.wolfram.com/SumofSquaresFunction.html) for the number of ways of expressing a number as the sum of two squares. You can do the same thing for the circle centered at $(0,\frac{1}{2})$ or $(\frac{1}{2},\frac{1}{2})$. You can then do an optimization to find the largest value where this distance is less than $n/2$. I expect that this will be possible in polynomial time using dynamic programming.

I cannot imagine that the largest value would not correspond to the center having coordinates other than $0$ or $\frac{1}{2}$, but this should be proved.

> **Comments:**
> **username_0**: thanks for your quick answer! Experimentally, the optimal circles were always centered around either 0 or 1/2. Any hints about how would one prove this?  
> **username_1**: I don't know how one would prove this; I don't even know if it's true. It is true that the largest exponent on a prime required is order $\log \log n$, which means that exhaustive search can find the optimum answer in pseudopolynomial time $\log^{(\log\log n)} n$, which is still a lot better than factoring. I thought this could be sped up to polynomial time by dynamic programming, but I'm not sure that's right.  
> **username_1**: Addendum to previous note: a clever exhaustive search algorithm can find the optimum answer in time $(\log n)^{O(\log\log\log n)}$.  
> **username_0**: Thanks again Peter! I wonder if an exhaustive search is unavoidable for this problem. At this point, the problem is close enough to P but not there yet :-) I will try to look for a randomized solution.  
> **username_1**: I still don't know how to show the optimal circle is centered around 0 or 1/2, either.  
> **username_0**: It's actually not true that the optimal circles are centered around points with coordinates 0 or +/-1/2. Sorry for my first comment (my simulation results show other points too).  
> **username_1**: @Ramzi: interesting. What kind of points are they centered around?  
> **username_0**: for a given $n$, there are often many optimal circles, some of which are not centered around a point in $\{-1/2,0,1/2\}\times\{-1/2,0,1/2\}$ . But it is true (of course according to simulations) that among those optimal circles, there are always some centered around elements of $\{-1/2,0,1/2\}\times\{-1/2,0,1/2\}$. For instance, for $n=5$, optimal circles contain $4$ lattice points, and the circle of center $(0,1)$ and radius $1$ is one of them. For $n=9$, the circle of center $(3/2,3/2)$ and radius $5/2$ is also optimal (contains $8$ lattice points).  
> **username_0**: BTW, for both examples, the point in the middle of the grid is the origin $(0,0)$. I also noticed that whenever a solution is unique, the center of the optimal circle always belong to $\{-1/2,0,1/2\}\times\{-1/2,0,1/2\}$.  
> **username_1**: Hi Ramzi: I didn't make myself clear; what I meant to say was that the center of all optimal circles would be at integer or half-integer coordinates, not 0 and 1/2, despite that being what I said. Sorry.  
> **username_0**: Thanks for the clarification Peter! At this point, what you've conjectured seems to be consistent with my simulation results.  
> **username_0**: I think the following properties seem to hold: (1) The number of lattice points in an optimal circle is a multiple of 4, (2) The radius squared of an optimal circle is either an integer or half integer, and (3) There's always an optimal circle centered around (0,0) or (1/2,0) or (1/2, 1/2).  

---

