Date: Mon, 9 Sep 1996 14:51:38 -0400 (EDT) From: "Eric Ruth (MTH)" To: Dave Rusin 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