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?
1
-
1$\begingroup$ This is somehow related to cstheory.stackexchange.com/questions/8406/… $\endgroup$– RamziCommented Nov 28, 2011 at 19:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
12
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.
answered Nov 28, 2011 at 19:20
-
$\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$– RamziCommented Nov 28, 2011 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$ Commented Nov 29, 2011 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$ Commented Nov 30, 2011 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$– RamziCommented Nov 30, 2011 at 3:52
-
$\begingroup$ I still don't know how to show the optimal circle is centered around 0 or 1/2, either. $\endgroup$ Commented Nov 30, 2011 at 3:53