# 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

## 1 Answer

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.

• My fear was that this question was a homework question: that's why I asked for the motivation . – Suresh Venkat Jun 11 '14 at 22:11
• Thanks. That's what I was looking for. Didn't know there was a similar problem with a name. I thought about something like Edelsbrunner and Welzl (1986) viewed in terms of k-sets of point sets but couldn't formalise it. Time to learn about bitangents! – Jayen Jun 12 '14 at 0:28