Services & ResourcesWolfram ForumsMathGroup Archive

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

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>