From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.research,sci.nonlinear
Subject: Re: Covering problem - reference please?
Date: 8 Sep 1995 05:59:02 GMT

In article <42li1i$e8l@dingo.cc.uq.oz.au>,
phil diamond <pmd@maths.uq.oz.au> wrote:
>I am trying to find estimates for the minimal number 
>of points in an \epsilon - net for the sphere S^{k-1} 
>in \Re^k. This is equivalent to the minimal number of
>balls of radius \epsilon, with centres on the sphere, 
>which cover it. The answer is obviously O(\epsilon^{1-k}). 
>I can easily see the lower bound, but cannot immediately 
>justify the upper bound. 

Perhaps the moderator will squelch this if I'm missing something deep
here, but you seem to be asking for a demonstration that it is
possible to find  O(epsilon^(1-k)) points on  S^{k-1} such that every
point on the sphere is within a distance of  \epsilon  of one of the points.

Why not just proceed by induction: given such an array  {P_n}  of points
on  S^{k-2}  such that every point is at most  \epsilon/2  from some P_n,
take a number of copies of this to get an array on the cylinder
[-pi/2, pi/2] x S^{k-2}  (that is, use the points  (-pi/2 + m \epsilon/2,  P_n)
where  m  runs from  0  to  2pi/\epsilon). Then from any point on the
cylinder you need only run a distance at most  \epsilon/2  to reach one
of the copies of  S^{k-2}, and then at most a distance  \epsilon/2  to one
of the  P_n  on that copy of  S^{k-2}.  Once you have this arrangement
of points on the cylinder, fold everything in to  S^{k-1}, that is,
send  (t, z)  to  (sin(t), cos(t) z); this just reduces length.

This procedure starts with  2pi/\epsilon  points on the circle and
constructs  8pi^2/\epsilon^2  points on  S^2, then 64pi^3/\epsilon^3
points on S^3, and in general  2^{k(k-1)/2} (pi/\epsilon)^{k-1}  points 
on  S^{k-1}. Of course this is nowhere near the best constant (already
there are too many points near the poles of  S^2)  but the exponent
on \epsilon is right. If you do need to get the right constant, you're
asking for an equidistribution of points on spheres, which is more
complicated. (I can give you some pointers if that's what you need.)

dave

==============================================================================

From: WimmerLienha@edvz.sbg.ac.at (your_name)
Newsgroups: sci.math.research,sci.nonlinear
Subject: Re: Covering problem - reference please?
Date: Fri, 8 Sep 1995 15:33:00 GMT

In article <42li1i$e8l@dingo.cc.uq.oz.au>, pmd@maths.uq.oz.au says...
>
>I am trying to find estimates for the minimal number 
>of points in an \epsilon - net for the sphere S^{k-1} 
>in \Re^k. This is equivalent to the minimal number of
>balls of radius \epsilon, with centres on the sphere, 
>which cover it. The answer is obviously O(\epsilon^{1-k}). 
>I can easily see the lower bound, but cannot immediately 
>justify the upper bound. The estimate is apparently well 
>known (to those who know it well) and extends to any 
>(n-1)-dimensional compact manifold. 
>

This problem seems to be connected with the following: place n congruent 
circles on the surface of a sphere, so that they cover the surface, and that 
their radius is minimal. This problem was treated by L.Fejes-Toth [1,2], who 
proofed an inequality, giving solutions for n = 3,4,6,12; G.Fejes-Toth [3] 
solved it for n = 10 and 14, and T.Tarnai & Zs.Gaspar [4] found a way to 
compute good point sets for n up to 20, but without any proof.

I hope these hints are a help for you, 
			
		Lienhard

Lienhard Wimmer
Inst. fuer Mathematik
Hellbrunnerstr. 34
A-5020 Salzburg
Austria/Europe

wimmerlienha@edvz.sbg.ac.at


[1] L.Fejes-Toth: Regular Figures, McMillan 1964

[2] L.Fejes-Toth: Lagerungen in der Ebene, auf der Kugel und im Raum
		  Springer, Berlin-Heidelberg-New York, 1956, 1972

[3] G.Fejes-Toth: Kreisueberdeckungen der Sphaere
		  Sci. Scientiarum Mathematcarum Hungarica 4 (1968), 225-247

[4] T.Tarnai, Zs. Gaspar:
^		  Covering a sphere by equal circles, and the ridity of its 
		  graph.
		  Math.Proc.Camb.Phil.Soc 110 (1991), 71 - 89