Menu
I'm writing a program that implements SCVT (Spherical Centroidal Voronoi Tesselation). I start with a set of points distributed over the unit sphere (I have an option for random points or an equal-area spiral). There will be from a several hundred to maybe 64K points.
I then need to produce probably several million random sample points, for each sample find the nearest point in the set, and use that to calculate a "weight" for that point. (This weigh may have to be looked up from another spherical set, but that set will stay static for any given run of the algorithm.)
Then I move the original points to the calculated points, and iterate the process, probably 10 or 20 times. This will give me the centers of the Voronoi tiles for subsequent use.
Later I will need to find a given point's nearest neighbor, to see what tile the user clicked on. This is trivially solved within the above problem, and doesn't need to be super-fast anyway. The part I need to be efficient is all those millions of nearest neighbors on the unit sphere. Any pointers?
Oh, I'm using x, y, z coordinates, but that's not set in stone. It just looks like it will simplify things. I'm also using C as I'm most familiar with it, but not wedded to that choice either. :)
I've considered using the spiral pattern for the sample points, as that gives me at least the last point's found neighbor as a good starting point for the next search. But if I do that, it looks like it would make any sort of tree search useless.
edit: [I'm sorry, I thought I was clear with the title and tags. I can generate random points easily. The issue is the nearest neighbor search. What's an efficient algorithm when all the points are on the unit sphere?]
976
You can only evenly distribute points on a sphere if the points are the vertices of a regular solid. So you can exactly evenly space 4, 6, 8, 12, or 20 points on a sphere. Oh, also there's the degenerate case of 2 antipodal points.
The average nearest neighbor ratio is calculated as the observed average distance divided by the expected average distance (with expected average distance being based on a hypothetical random distribution with the same number of features covering the same total area).
Nearest Neighbor Rule selects the class for x with the assumption that: Is this reasonable? Yes, if x' is sufficiently close to x. If x' and x were overlapping (at the same point), they would share the same class.
In approximately nearest neighbors (ANN), we build index structures that narrow down the search space. The implicit neighborhoods in such indexes also help reduce the problem of high dimensions. You can roughly divide the approaches used for ANNs into whether or not they can be implemented using an inverse index.
Your points are uniformly distributed over the sphere. Therefore, it would make a lot of sense to convert them to spherical coordinates and discretize. Searching the 2D grid first would narrow down the choice of nearest neighbour to a small part of the sphere in constant time.
113
You may find that organising your points into a data structure called an Octree is useful for efficient search for nearby points. See http://en.wikipedia.org/wiki/Octree
40
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
