Need an algorithm to pixelate an n-dimensional hypersphere.

Question

I would like to bin vectors in n-dimensional space. This can be done by pixelating the surface of an n-dimensional hypersphere.

Does anyone know any good algorithms for pixelating a hypersphere in C? I would like constant bin sizes. My space consists of only positive integers.

Answer 1

Do you need your bins to be perfectly regular? If not, just throw points out at random, and measure distance to the nearest neighbor. You could clean this up slightly by throwing away points that are too close, or running a few iterations of mutual repulsion.

Otherwise, you probably want to convert to generalized spherical coordinates and bin into equal areas along each dimension. In particular, if you know you're in bin 5 of 20 on longitude, your latitude bins will be wider than they would be at the equator (about sqrt(2) wider in angle, in fact, to correspond to the same distance on the surface).