Sunday, July 6, 2014

Pick's Theorem and Gauss's Circle problem

Gauss's circle problem asks a question that at it's heart concerns how many integer lattice points are inside or on the circle on a grid:
Above if you counted them all there would be 113.
For a close estimate I did the following:
Here I've drawn a shape that is only 4 away from containing every lattice point inside or on it's boundary. 
It's perimeter has to be (r-1)*8, above for r=6. Because you eventually will have gone up 5*2 times down 5*2, right 5*2, left 5*2... which is 5*8. 
You can see that the area of the red figure should be somewhere between pi*5^2 and pi*6^2 because it lies between both circles at all times. 
So for a figure like the red figure we can use Picks theorem to figure out the number of points inside and on the boundary of the red figure...
This relates the area, which we will approximate, the number of interior points i and the number of boundary points.
So for our red figure the estimate works out to:

So for example, a circle with radius 46 would have around 6683 by this estimate, the actual value is 6625 so the estimate is within 1%.
**Note** it's also possible to figure absolute upper and lower bounds by using the outer or inner circle, the estimate above just averages the lower and upper bound together...
I only showed for the circle, but the general idea could apply to ellipses or other shapes with known areas or number of lattice points under a curve, etc...

No comments:

Post a Comment