[Date Index] [Thread Index] [Author Index]

Re: intersecting a hypercube and a hyperplane

• To: mathgroup at smc.vnet.net
• Subject: [mg88985] Re: intersecting a hypercube and a hyperplane
• From: juan flores <juanfie at gmail.com>
• Date: Fri, 23 May 2008 03:05:41 -0400 (EDT)
• References: <200805211854.OAA10662@smc.vnet.net> <g134fd$m1g$1@smc.vnet.net>

On May 22, 1:39 am, Daniel Lichtblau <d... at wolfram.com> wrote:
> juan flores wrote:
> > 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
>
> Use linear programming, e.g. as LinearProgramming or NMinimize, to find
> all extremal points in the cube subject to lying on the plane.
>
> The hypercube can be written as 2*n inequalities, in pairs of the form
> low_j<=p_j<=high_j, where p_j is a linear expression and the normals to
> these expressions are all pairwise orthogonal. In the "nice" case, they
> are simply coordinates, that is, inequalities are low_j<=x_j<=high<j.
> Anyway, this gives 2*n linear programs to solve in order to get all
> extremal points. Some may coincide, so take the union.
>
> You might be able to bypass all this by directly calling NMinimize on
> your actual objective function. Just pass the relevant constraints and
> let NMinimize try to figure out your optimum. If you give explicit
> Method->"DifferentialEvolution" then it will be using an evolutionary
> algorithm (or, at least, an algorithm with "evolution" in its name; it's
> the appearance that matters, I'm told).
>
> Daniel Lichtblau
> Wolfram Research

Thanks, Daniel.  I will give it a try.

Juan

• References:
  • intersecting a hypercube and a hyperplane
    • From: juan flores <juanfie@gmail.com>