From: Wim van Dam <Wim.van.Dam@qubit.org>
Newsgroups: sci.math.research
Subject: Q: covering/pixelizing a HYPERsphere
Date: Tue, 08 Sep 1998 19:05:23 +0100

Dear all,


I checked it, and this one is not sufficiently answered in the FAQ,
nor somewhere else on the web (it seems) so here goes:

Given epsilon and N:
  "How many points do I need to cover the surface of a unit N-sphere
   such that every position on that surface has a distance less
   than epsilon to one of those points?"

Another way of looking at this is that we paint (N-1)-spheres with
radius epsilon on the surface of an N-dimensional hypersphere of
radius 1: how many spheres do we have to paint in order to cover
the whole N-sphere?

It looks like an obvious question to me, but almost all the research
seems to concentrate on the N=3 case in great detail. 
Where can I find some bounds (even asymptotic) for general N?

Any help/pointers will be much appreciated and acknowledged.


Cheers,

Wim van Dam
==============================================================================

From: Dave Rusin <rusin@math.niu.edu>
Date: Mon, 14 Sep 1998 10:37:22 -0500 (CDT)
To: wimvdam@qubit.org
Subject: Re:  covering of a hypersphere

You asked about pointers to an equal covering of N-dimensional spheres.
This topic is intimately related to sphere-packing and the study of
N-dimensional lattices, all of them covered in a book by Conway and Sloane.

If all you want to know is roughly how far apart you can set points on
an  N-sphere, you might want to consider the Voronoi regions: simply
look at the points on the N-sphere closer to a given point  P  in the set
than any of the other points; if your  k  points are distributed in a 
fairly uniform way, each of these  k  regions will be of similar size
and will roughly approximate a little  N-dimensional  ball if the
number of points  k  is large enough (For example, a golf ball appears to
be subdivided into a large number of small planar disks). Since the
N-volume of a unit N-sphere is   (N+1) pi^((N+1)/2)/gamma((N+1)/2 + 1) 
and the N-volume of the N-ball of radius  r  is  pi^(N/2)/gamma(N/2 +1) * r^N,
we deduce that the "average radius" of the Voronoi regions (sort of the
average distance between nearest pairs) is about  C/ k^(1/N)  with
C roughly  exp( log(2Pi/N)/ 2N )  for large  N. 

Put the other way, if every point is about a distance  r  from its
nearest neighbor, the number of points would be about B/r^N where  B is 
roughly sqrt(2Pi/ N) for large N.

dave