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?