2
$\begingroup$

I don't think this is a pure math problem, so I post it here.

Assume we have two regions in $\mathbb R^n$: $$ \lbrace x : a \leq x \leq b \rbrace\\ $$ and $$ \left\lbrace x : \sum_{i=1}^n |x_i | \leq c \right\rbrace $$

The problem is to find the smallest possible cube that contains the intersection between the two regions.

If $x \in \mathbb R^2$, then the first region is a square and the second a diamond-shape, and the problem looks something like this (the red square is the solution to the problem):

enter image description here

The problem is reasonably easy if one takes a particular case like the one on the picture. We can find the equation for the line that crosses the square and find the $x$ and $y$ values where the line is equal to the constants signifying the sides of the square. However, which sides of the square we use depends on the position of the square (it can even be crossed by several lines). In general, it seems to be a lot of special cases to deal with by going that route.

I am wondering if there are general procedures that can be applied to this problem, or if anyone knows an elegant solution to this particular one.

$\endgroup$
3
$\begingroup$

Here is a suggestion. Partition your problem into two parts: (1) Construct the intersection, (2) Find the smallest cube.

(1) The intersection is a polytope defined by the union of your inequalities for both shapes. This is known as an H-representation of the polytope. There is software for constructing a polytope from its H-representation. polymake is one option. Essentially you want to convert your H-representation to a V-representation.

(2) This is the easier half. Find the smallest bounding box from the extreme vertex coordinates. Then fatten the box to a cube.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.