Partial ideas:1. The solution is NOT unique in most situations -- a range of planes (delimited by a frontier on the partitioned points) will solve the problem.*2. A solution plane will pass within epsilon of 2 of the points. One solution process might be to consider all possible point pairs and the partitions they create. BTW, this proves that the worst-case partition has N/2-1 and N/2+2 points in it.*.... more later....* there's always the possibility of degenerate configurations.

P.S. My comments apply to 3-spheres. Hyperspheres may have different properties. For example a 4-spheres will have partitions that pass within epsilon of 3 points.

QuoteOriginally posted by: outrunIs it about finding two specific point to span the plane (the 3rd point being O)?Exactly! A plane through the origin and those two points will partition the sphere. It's just a matter of finding the two points that create a greatest inequality of the partition and then nudging the plane by epsilon to one side of the two points.With a bit of extra labour in finding all point pairs than produce an equivalent maximal partition, one can determine the bounds on the entire space of solution planes which will be the inverse of a mirrored convex polygonal cone. (Of course, there might be multiple such inverse-cones!)

My first idea would be find the average location of the set of points that is each point projected onto the surface. And then position the plane so that it faces that average location.For example, consider we have two points that are near the middle next to each other, and a third point that is way out toward the surface of the side opposite the two points. An average position would be between the far-out point and the origin. But if we move the points near the middle to the surface by shining a flashlight out from the origin, the average of those three surface points will be near those first two points. So if we position a plane that faces that spot, it will put those two on one side as it should.

QuoteOriginally posted by: outrunthere are some very fast (but a bit conplicated) numerical algorithms for it.It is not that complicated, and I see no opportunity for shortcuts, so those algorithms must do something else, like find the optimal origin, or find approximations in non spheres.

They key to it is you have extra information, describing the distance of each point from the origin, which is useless because you can't move the plane off the origin. So you just filter that out, and keep only their position around the circle, to decide how to rotate the plane around the circle.

QuoteOriginally posted by: outrunIf all neighbors are to the right, then you move that direction. If you are in the middle of the crowd, then you stop moving.I think if you have n points, you can find their middle in n-1 steps. Start by taking the average position of points j and k. Then find the average of that point and point v, but giving a two-third/one-third weighting. Or if you have an even number of points, pair them off and find the average of each pair. Repeat until you don't have an even number, and then use the weighting.If you want n clusters, then you just average each point with its closest point, and always average lowest-weighted points first, until there are n weighty points left where you want n clusters. Or if you want n to be dictated by the natural clustering, keep averaging the lowest-weight points with their closest neighbors, but only do so if the distance is below a maximum. Or if the distance is below a maximum that is a function of their combined weight.

May be a solution with spherical coordinates could be simpler. I could be wrong here but my intuition stemmed from a simpler 2d version of this problem. In 2-d this question would be equivalent to splitting a circular area x^2 + y^2<=1 into 2 parts with a line through (0,0) so as to maximize the difference in points belonging to each part. In circular coordinates, r & θ, if max θ < π then the line is the x-axis, else choose an angle θ such that maximum points are in the range [θ,π+θ]. The radial coordinate is not useful here. I am not very sure if this can be extended to the spherical coordinates with polar and azimuth angles.

Hi Jointy,this is going the right direction for 2D. But more precisely, for this problem you don't need to havethe full coordinate information. You can project the 2d coordinate to the azimtual angle of each point.Now what you do is, you collect the partial sums of these angles. Now you look at the combinations that maximize the amount of pointswhile staying below 180 degrees. Than you can be sure that a plane can separate them from the rest. This is the solution and there can be nobetter separation, otherwise we would necessarily exceed 180 degrees. actually constructing the partial sums is not really combinatorially expensive if you keep track of relative distances and so on. It is fairly straightforward to extend this to 3D. You now have two angle. Again keep the partial sums of relative azimuts below 180 degrees and the altitude 90 degrees.