MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a hypercube in n-dimensions, and take some projection down to an m-dimensional subspace. Now take all vertices and m-1 dimensional facets visible from some direction outside the projection. Project these down to an appropriate m-1 dimensional subspace and you have a tiling of a topological ball in that space.

My question is, what is a reasonably efficient algorithms to select the correct points in m-d? Obviously part of this problem is to find a convex hull, though there is more information available that just the point cloud. In particular we know the position of each point in the original hypercube and so the edges connecting it up to its neighbors. If the conical hull of these edges is a cone, and not the whole space it lies on the convex hull of the projection.

Checking whether the conical hull of the edges plus the view direction formed a cone or the whole space would select the required points. It would therefore be sufficient to have a quick method to determine if the conical hull of a given set is a cone or the full space.

Note: I am dealing with fairly small numbers of points and low dimensions (3 and 4 to be precise, the pictures are better there) so easy to implement algorithms will be as useful as computationally fast ones.

share|cite|improve this question
Likely I do not fully understand your situation, but it seems that you can determine whether the conical hull is a cone or the full space by checking if the origin falls strictly inside the convex hull. Since your $n$ and $d$ are small, you could just compute this hull and check the origin. – Joseph O'Rourke Nov 9 '11 at 19:40
That is true, and how I have implemented it, but part of me feels that finding the convex hull is overkill. – Edmund Harriss Nov 9 '11 at 20:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.