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