2
$\begingroup$

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?

$\endgroup$
1
6
$\begingroup$

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 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.

$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – Ramzi
    Nov 28 '11 at 22:03
  • $\begingroup$ 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. $\endgroup$ Nov 29 '11 at 3:00
  • $\begingroup$ Addendum to previous note: a clever exhaustive search algorithm can find the optimum answer in time $(\log n)^{O(\log\log\log n)}$. $\endgroup$ Nov 30 '11 at 1:19
  • $\begingroup$ 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. $\endgroup$
    – Ramzi
    Nov 30 '11 at 3:52
  • $\begingroup$ I still don't know how to show the optimal circle is centered around 0 or 1/2, either. $\endgroup$ Nov 30 '11 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.