<p>If I understand well, you are interested in the $k$-set problem:
<a href="http://en.wikipedia.org/wiki/K-set_%28geometry%29" rel="nofollow">http://en.wikipedia.org/wiki/K-set_(geometry)</a></p>

<p>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.</p>

CC BY-SA 3.0
2014-06-11T22:11:37.937Z
My fear was that this question was a homework question: that's why I asked for the motivation .
Suresh Venkat
CC BY-SA 3.0
2014-06-12T00:28:37.133Z
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
CC BY-SA 3.0
2014-06-11T17:42:13.420Z
2014-06-11T17:42:13.420Z
domotorp
<p>I have a series of <code>n</code> points in <code>d</code>-dimensional continuous space.  I want to find a series of hyperplanes such that <code>k</code> points are below the hyperplane and that the set of <code>k</code> points below each hyperplane is a unique set.  It does not matter what the hyperplane is (e.g. if it connects <code>d</code> 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.</p>

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

<p>Is there a better way?  What is it?</p>

CC BY-SA 3.0
2014-06-11T11:41:59.373Z
Why do you want to compute this ?
Suresh Venkat
CC BY-SA 3.0
2014-06-12T00:26:39.403Z
It's a component of an algorithm for work
Jayen
<cg.comp-geom>
Find all hyperplanes separating unique sets of `k` points
Jayen
# Find all hyperplanes separating unique sets of `k` points

(Asked by: username_0 on 2014-06-11)

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?

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: Why do you want to compute this ?  
> **username_0**: It's a component of an algorithm for work  

---

## 1 answers

### Answer by username_2 on 2014-06-11. Score: 1 | Accepted answer

If I understand well, you are interested in the $k$-set problem:
[http://en.wikipedia.org/wiki/K-set\_(geometry)](http://en.wikipedia.org/wiki/K-set_%28geometry%29)

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.

> **Comments:**
> **username_1**: My fear was that this question was a homework question: that's why I asked for the motivation .  
> **username_0**: 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!  

---

