analytics

Thursday, August 1, 2013

Estimation of Gauss's circle problem

Gauss's circle problem asks how many grid points are inside a circle of a certain radius, like here we have a circle of radius 8 and if you count the number of points lying exactly on the circle and inside you find that there are 197.
A list of the first 46 such numbers and a plot:
Now I've found this function that closely approximates this curve:
For instance a circle with radius 46 has 6625 points inside it and on the boundary, my formula gives: 6650. So within a couple thousands of a percent of the true value.

**Derivation**
I start with a couple of assumptions, that the number of points actually on the circumference of the circle goes up exactly as the radius. This is not exactly true but close enough to give the result I wanted. Also that these points can be approximated by a n-gon where n is the radius. For example here is the circle of radius 8 and the octagon I use to represent the number of points on the circumference of the circle....

Now I arrived at this set of equations and their solution:

I'll number and expalin each:
1.Pick's Theorem: that the area of the n-gon is equal to the number of grid points in the interior of the n-gon, i, plus half the number of points on the boundary b -1.
2. The area C + 4*x where x is each corner area outside the polygon but inside the square is equal to twice the radius squared for the area of the whole square.
3. The third is saying that C the area of the n-gon related to the number of points on the boundary and the radius (both represented by b because remember I assume the number of sides of the n-gon, and the radius are the same) and using the usual formula for the area of such a polygon.
4.An equation for x, the area in one corner outside the n-gon. Introducing i2 for the interior of this region, b2 for the border, and using picks theorem again.
5. This follows from the fact that b and b2 share a common border and that if you if you subtract one quarter of the inner border from outer you are left with just the semi perimeter of twice the length of the square.
6. That 4 times the border of the corner polygons minus the border of the n-gon is 8 times the radius, or the perimeter all the way around the square.

So the solution gives an expression for i  which is the number of interior points, to which for the final equation I add one b so it becomes an expression for the interior plus the points on the border,  and we give the equation b the radius and it ends up closely estimating the number of grid points within and on the border of the circle.


No comments:

Post a Comment