When is the conical hull of a finite set of vectors a subset of the space? (and tilings) - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T04:29:27Z http://mathoverflow.net/feeds/question/80509 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80509/when-is-the-conical-hull-of-a-finite-set-of-vectors-a-subset-of-the-space-and-t When is the conical hull of a finite set of vectors a subset of the space? (and tilings) Edmund Harriss 2011-11-09T19:17:29Z 2011-11-09T19:17:29Z <p>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.</p> <p>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.</p> <p>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.</p> <p><strong>Note:</strong> 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.</p>