Date: Mon, 9 Sep 1996 14:51:38 -0400 (EDT)
From: "Eric Ruth (MTH)" <eruth@chuma.cas.usf.edu>
To: Dave Rusin <rusin@math.niu.edu>
Subject: Re:  Distributing points on sphere

September 6, 1996

Dave Rusin,

        Do you have any information on evenly distributing points on a
disk, or an ellipsoid, or other objects?

Sincerely,

Erich Ruth
eruth@chuma.cas.usf.edu
==============================================================================

Date: Mon, 9 Sep 96 14:20:18 CDT
From: rusin (Dave Rusin)
To: eruth@chuma.cas.usf.edu
Subject: Re:  Distributing points on sphere

You wrote:
>        Do you have any information on evenly distributing points on a
>disk, or an ellipsoid, or other objects?

Depends what you want to know. If you want to know about provably optimal
results, then the answer is uniformly 'no'. If you want to know about
reasonably effective means to distribute large numbers of points uniformly
then the answer is 'not offhand, but I can surely create something'.

For example, the disk is trivial: it's a portion of the plane, so one need
only distribute points uniformly across the plane (e.g. in a hexagonal 
grid) and discard the points outside the disk. The area over which this
fails to be optimal (around the edge) can hold a number of points roughly
proportional to the square root of the number of points distributed on the
whole disk; thus as the number of points increases, this planar distribution
grows increasingly close to optimal.

On an ellipsoid, I guess I would mimic a naive approach used for the
sphere: partition the shape into a number of parallel and equally
spaced shapes (circles or ellipses), then place on each of these (with
uniform spacing) a number of points proportional to the length of that
shape. Probably one could even estimate how far short this method would
fall from an optimal distribution (assuming a measure of optimality has
been agreed upon).

Shapes with no particular symmetry are harder. I suppose I could handle
any shape homeomorphic to a sphere, for example (that is, anything which
results from continuous deformation of a sphere, like a potato); again
I would not expect satisfactory results unless the number of points to
be placed is large compared to the curvature. What I would do is to
cover the shape with a number of disks, on each of which the curvature
varies sufficiently little that the disk resembles a portion of a
sphere or a plane. Then one could use a fairly regular distribution of
points on each of those disks, and do just about anything on the overlaps
(assuming the overlaps are just curves rather than 2-dimensional subsets);
again we rely on the fact that the fraction of points which are near
these edges will decrease to zero as the number of points place grows 
without bound.

If you have some specific task in mind, let me know.

I assume you have seen the related material in
	index/spheres.html
[URL updated 1999/01 -- djr]
which includes a couple of pointers to the literature. Perhaps I should
remind you that I don't work in this area professionally; in particular, 
there may indeed be some results in the literature which answer the
questions you ask.

dave