From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Holes on a sphere Date: 8 Nov 1994 17:08:12 GMT In article <39mrqm$8f1@usenet.ins.cwru.edu>, John Barmann wrote: > >I have a geomety/math/CAD probelm that i can't seem to crack. I need >to space 14,000 to 15,000 holes on a sphere. The sphere has a diameter >of 8.125 inches and is hollow. The holes are to be .098 inches in "spaced equally" isn't an agreeable notion on a sphere, but I think I understand your intention. With so many holes to place, why not just arrange them along parallel circles, starting at the north pole? To place N holes on a sphere of radius R leaves each one surrounded by an area of 4 pi R^2 / N, equivalent to a disc of radius 2R/sqrt(N) around each. I would draw discs of this radius around each pole, then draw bands of width 4R/sqrt(N) around them, and space the points along the centers of the bands at distance of about 4R/sqrt(N) apart. (There are a lot of round-off problems to address, though it sounds like you're not particular as to the exact number of holes or an exactly uniform placement. If you do need to improve this distribution you could model this as a bunch of charged particles floating on the surface of the sphere and watch them repel each other, and take their resting places as the centers of your holes.) In standard spherical coordinates (phi, theta), place your first point at phi=0 (theta undefined there). Subsequent points are placed at phi = (k/M) pi (k=1, 2, ..., M), where M is an integer close to (pi/4) sqrt(N) (say M=100); take points with theta coordinates theta= (j/Q) (2 pi) (j=1, 2, ..., Q) where Q is an integer close to 2 M sin(phi). This gives two poles and M-1 bands of points having between 6 and 2M points on them. Taking M=100 gives 12731 points; perhaps M=106 or so would match your criteria better. (These angles are in radians of course.) dave ============================================================================== Newsgroups: sci.math From: asimov@geom.umn.edu (Dan Asimov) Subject: Re: Holes on a sphere Date: Wed, 9 Nov 1994 15:35:48 GMT In article <39mrqm$8f1@usenet.INS.CWRU.Edu>, John Barmann wrote: > >I have a geomety/math/CAD probelm that i can't seem to crack. I need >to space 14,000 to 15,000 holes on a sphere. The sphere has a diameter >of 8.125 inches and is hollow. The holes are to be .098 inches in >diameter and are to be spaced equally on the sphere. It's kind of >like a wiffleball a golfball. > >I need a formula to plot the center points of these holes. X,Y,Z >coordinates or any other solution that can be modeled on CAD in >3D would be fine. > >If I can get this to work, it will be part of a space experiment >that will fly on the space shuttle in 18 months. A solution >is needed asap. > >Thanks --------------------------------------------------------------------------- This question of how to find "equally spaced points on a sphere" comes up regularly on sci.math to the point that it is perhaps a candidate for inclusion in the F.A.Q. file. One problem with this question is that the concept of "equally spaced points on the sphere" is not well-defined. Certainly it doesn't mean that the distance bewteen any two points is the same. This definition will limit you to 4 points, maximum. It might mean that "any two points "look the same" in the sense that for any points p and q in our set, there is a rotation of the sphere taking the set to itself and taking p to q. However, if this is the case, then the Voronoi regions of any point p (all points of the sphere closer to p than to any other point of our set) must be congruent. With one class of exceptions, this almost certainly limits the size of our set to be no more than several hundred. The exceptions are all the tessellations of the sphere by congruent sectors ("orange slices"), or half-sectors. This arrangement is probably not satisfactory from the point of view of wanting the points to spread out as uniformly as possible. So, to approach this problem from a practical point of view, let us ask if we can find N points on the sphere (N large) satisfying two conditions: 1. The minimum distance d(p,q) among all pairs of points is as large as possible, and 2. Let d_p denote the minimum distance d(p,q) form p to any other point q. Then we would like d_p to be "as constant as possible,' or in other words to have a standard deviation as low as possible. The first thing to say is that there are probably many other conditions that could be substituted for these two, and would probably result in at least slightly differing solution. The second thing to say is that by simply trying to attain condition 1., we may end up satisfying condition 2. to a sufficiently good approximation. So, here is a possibly useful algorithm which would require a great deal of compute power to implement in any reasonable time if N is around 14,000: (But since the solution may not be needed until May 1996, there might be enough time to use this method!) 1. Pick N points at random on the unit sphere. Call the set of points S. 2. Note that S may be considered to be one point in 3N dimensional space (or one point in 2N dimensional space if longitude and latitude are used; this may save computation). Define f(S) to be the minimum distance d(p,q) among all pairs of points p and q. (For computation's sake, it's easiest to take the "distance" d(p,q) to actually be the square of the Euclidean distance from p to q; the end result will be the same.) 3. Now use numerical techniques to maximize f(S). Warning: f will be a continuous function of S (as a point in R^3N or R^2N as above), but will NOT be a differentiable function of S. So a naive approach based on just following the "gradient" of S may be doomed to failure. Daniel Asimov Senior Computer Scientist Computer Sciences Corporation Mail Stop T27A-1 NASA Ames Research Center Moffett Field, CA 94035-1000 (415) 604-4799 w (415) 604-3957 fax ============================================================================== From: chrisman@ucdmath.ucdavis.edu (Mark Chrisman) Newsgroups: sci.math Subject: Re: Holes on a sphere Date: 10 Nov 1994 06:34:49 GMT In article asimov@geom.umn.edu (Dan Asimov) writes: > In article <39mrqm$8f1@usenet.INS.CWRU.Edu>, > John Barmann wrote: > > > >I have a geomety/math/CAD probelm that i can't seem to crack. I need > >to space 14,000 to 15,000 holes on a sphere. The sphere has a diameter > >of 8.125 inches and is hollow. The holes are to be .098 inches in > >diameter and are to be spaced equally on the sphere. It's kind of > >like a wiffleball a golfball. > > > >I need a formula to plot the center points of these holes. X,Y,Z > >coordinates or any other solution that can be modeled on CAD in > >3D would be fine. > > > >If I can get this to work, it will be part of a space experiment > >that will fly on the space shuttle in 18 months. A solution > >is needed asap. > > > >Thanks Here's an obvious approach which probably won't give the best answer, but which might give a good enough answer for you: Place the holes randomly on the sphere. Run a computer simulation in which the holes are particles that repel each other (by an inverse square law or something) and see what you end up with. You'll have to include some friction in the simulation to make the particles settle down. -------------------------------------------------------- Mark Chrisman "The number you have dialed is imaginary. Please rotate your phone 90 degrees and try again."