# Find all hyperplanes separating unique sets of k points

I have a series of n points in d-dimensional continuous space. I want to find a series of hyperplanes such that k points are below the hyperplane and that the set of k points below each hyperplane is a unique set. It does not matter what the hyperplane is (e.g. if it connects d points or if it is another hyperplane not intersecting any points). I can discretise the space if it helps. "below" is defined as the negative direction for the first dimension.

The way I have approached is to try all hyperplanes defined by all sets of d points, project each point on to this hyperplane, and test if the projection is above the point. This results in n^(d+1) complexity.

Is there a better way? What is it?

• Why do you want to compute this ? – Suresh Venkat Jun 11 '14 at 11:41
• It's a component of an algorithm for work – Jayen Jun 12 '14 at 0:26

If I understand well, you are interested in the $k$-set problem: http://en.wikipedia.org/wiki/K-set_(geometry)
In general their number can be $O(n^{\lfloor d/2\rfloor}k^{\lceil d/2\rceil})$ and though I could not find references now, I think you can also compute them in about this much time.