3
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Why do you want to compute this ? $\endgroup$ – Suresh Venkat Jun 11 '14 at 11:41
  • $\begingroup$ It's a component of an algorithm for work $\endgroup$ – Jayen Jun 12 '14 at 0:26
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ My fear was that this question was a homework question: that's why I asked for the motivation . $\endgroup$ – Suresh Venkat Jun 11 '14 at 22:11
  • $\begingroup$ 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! $\endgroup$ – Jayen Jun 12 '14 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.