From: fredh@ix.netcom.com (Fred W. Helenius )
Newsgroups: sci.math
Subject: Re: Counting points in a circle
Date: 11 Nov 1995 19:38:31 GMT

In <47pu8r$5bf@news.nznet.gen.nz> packrat@nznet.gen.nz (Packrat) writes: 

>I'm trying to use a square grid of points to measure the area of a 
>circle (we all have our little hobbies...) by laying the circle on the 
>grid and counting the points that lie inside the circle.
>To make things easier I use a cartesian plane, placing the circle at the
>origin and using a grid parallel to both axes. I only count points that
>fall _inside_ the circle, ignoring points that lie on the boundary of
>the circle (so that, for example, if my radius were 0, my "area" (number
>of counted points) would also be 0, not one). A circle of radius 1, for
>example, would have only one point within it (the origin), and so have
>an "area" of 1, even though there are four points on the edge.
>My question is, how fine do I have to make my grid for this method to be
>accurate to, say, n decimal places?

This is a problem with a lot of history; it's often called "Gauss's
lattice point problem".  There's a nice description of the problem
in Richard Guy's "Unsolved Problems in Number Theory" (2nd ed.);
for more information, see the references there.  A summary:

The number of lattice points within a circle of radius r centered
at the origin is approximately pi*r^2.  If we call the difference
between this ideal value and the actual value h(r), it is conjectured
that h(r) is O(r^(1/2 + eps)), for any eps > 0.  The best result so
far is that h(r) is O(r^(46/73 + eps)), due to Martin Huxley.  Hardy
and Landau showed that h(r) is _not_ o(r^(1/2) (ln r)^(1/4)).

[If the notations are unfamiliar:  f(x) is O(g(x)) means that
|f(x)| < c g(x)  for some constant c, for all x sufficiently
large.  Loosely speaking, f(x) has the same (or smaller) order of
growth as g(x), apart from a constant factor.

f(x) is o(g(x)) means  lim f(x)/g(x) = 0 as x goes to infinity;
so f(x) is, eventually, arbitrarily much smaller than g(x).]

--
Fred W. Helenius    <fredh@ix.netcom.com>