intersecting a hypercube and a hyperplane

*To*: mathgroup at smc.vnet.net*Subject*: [mg88941] intersecting a hypercube and a hyperplane*From*: juan flores <juanfie at gmail.com>*Date*: Wed, 21 May 2008 14:54:54 -0400 (EDT)

Hi all, I have a problem you will laugh about (maybe). Here: You have a hypercube and a hyperplane. They intersect. In n-D the intersection region is a (n-1)-D object. I am interested in determining the vertices of the intersection object. Of course, I can check all the edges and determine all intersection vertices, but that takes n 2^(n-1) checks. Do you know of any algorithm to compute that? The hyperplane is Sum(Xi)=C, for some C, where Xi is the i-th coordinate. Idea: For each vertex of the hypercube you add its coordinates, and form a partition into three sets (vertices behind, at, and in-front of the hyperplane). That information would allow you to restrict the search to edges involved in two of those sets. The problem is the preprocessing time (to compute the sum for every vertex) itself is exponential on n. I need something more efficient than exponential, or else, a pointer that indicates that no such algorithm exists. This comes from an optimization problem. The hypercube is the search space and the hyperplane corresponds to a energy conservation constraint. I am using an evolutionary computation technique, and are interested in generating a population of points that lie in the intersection. Any pointers/ideas will be greatly appreciated. Juan Flores Univesity of Michoacan, Mexico

**Follow-Ups**:**Re: intersecting a hypercube and a hyperplane***From:*Daniel Lichtblau <danl@wolfram.com>