2

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.

KeatsKelleher
  • 10,015
  • 4
  • 45
  • 52
  • 1
    Could you clarify? By "pixelate", do you mean "divide the surface up into regions"? Does this imply that all the input vectors lie on the surface? – Oliver Charlesworth Aug 31 '10 at 21:03
  • Thanks for your comment, yes; the surface should be divided up into regions of equal surface area. Each of the vectors is orthogonal to the surface. – KeatsKelleher Aug 31 '10 at 21:04
  • You potentially need more constraints than that to define an algorithm. For instance, imagine dividing a 3-dimensional sphere into 8 regions. You could do 8 north-south strips, or you could do 8 "corners" (i.e. dividing lines on the equator, the Greenwich meridian, and at longitude 90/270 degrees). And that's assuming they must all be the same shape... – Oliver Charlesworth Aug 31 '10 at 21:09
  • Sorry, I thought equal size and shape was implied by the term 'pixelate'. – KeatsKelleher Aug 31 '10 at 21:14
  • Ok, but the point remains! There's more than one way to do this. The "north-south" approach (well, it's n-dimensional equivalent) is arguably the most trivial, but may not be what you want. – Oliver Charlesworth Aug 31 '10 at 21:27
  • @Oli: I'm guessing the OP wants something similar to a geodesic sphere. – Cascabel Aug 31 '10 at 21:55
  • @Oli: Any approach that will pixelate the surface with m bins of equal size and shape, or even just equal size would be fine. – KeatsKelleher Aug 31 '10 at 22:06
  • @Jefromi: Quite possibly. However, to do so would be much more complicated. It's possible he just wants a way of dividing a set of vectors into subsets of roughly equal size, in which case my trivial example may be good enough... – Oliver Charlesworth Aug 31 '10 at 22:07
  • The latitude/longitude approach gives widely varying size from 'pole' to 'equator' which yields a little too much error. – KeatsKelleher Aug 31 '10 at 22:08
  • 1
    @akellehe: My "trivial" north-south suggestion was to bin based on longitude only. – Oliver Charlesworth Aug 31 '10 at 22:11
  • @Oli: interesting... This might work. Let me get back to it – KeatsKelleher Aug 31 '10 at 22:17
  • @Oli: I like the idea, it's very very fast compared to other possible solutions; but I feel there must be a more elegant solution out there. Rex's proposal is interesting. I'm going to try and work it out and see what the time complexity comes out to be. Your solution would be O(n), I believe; where n is the number of bins. Correct me if I'm wrong. – KeatsKelleher Sep 01 '10 at 14:02
  • @akellehe: By O(n), do you mean the complexity of calculating the binning? That should be O(1). Simply calculate longitude of your vector (simple trigonometry), and then quantise. I suppose that you could argue that you'd need to calculate `atan()` to an accuracy proportional to the number of bins, and so that would be O(n) if you need to use e.g. CORDIC. – Oliver Charlesworth Sep 01 '10 at 14:23
  • @akellehe: Correction: CORDIC is O(log n) with respect to accuracy... – Oliver Charlesworth Sep 01 '10 at 14:37
  • @Oli Charlesworth: In the case where one would use 1 dimension to draw bins one would still run into the issue of varying sized bins. – KeatsKelleher Oct 08 '10 at 16:23
  • @akellehe: Why? Can't you just set each segment to subtend the same angle? – Oliver Charlesworth Oct 08 '10 at 16:31
  • @oli: mm, oh yeah... That's right. It would work. – KeatsKelleher Oct 08 '10 at 16:39

1 Answers1

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).

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
Rex Kerr
  • 166,841
  • 26
  • 322
  • 407