3
$\begingroup$

Given $m$ number of convex polytopes each with $v$ vertices and described by $h$ hyperplane inequalities in $\mathbb R^t$ are there operations on these polytopes that combine then to give an $v^{\Omega(m)}$ vertex convex polytope describable by $O(hvm)$ hyperplane inequalities in $T=\mathbb R^{O(tm)}$ such that a point in $T=\mathbb R^{O(tm)}$ is in the new polytope implies its decomposition was in each of the $m$ polytopes?

$\endgroup$
3
  • $\begingroup$ Are you asking for the complexity of the intersection of $m$ convex polytopes? Or are you suggesting that there might be some other polytope $P$, different from the intersection, which nevertheless has the property that a point is in $P$ iff it is in each of the $m$ polytopes? $\endgroup$ Apr 22, 2019 at 23:28
  • $\begingroup$ @JosephO'Rourke Yes second. However I think only if is might not be possible. $\endgroup$
    – VS.
    Apr 22, 2019 at 23:28
  • $\begingroup$ Aren't you simply asking for "Cartesian product"? The Cartesian product of $m$ convex polytopes each with $v$ vertices and described by $h$ hyperplane inequalities in $\mathbb R^t$ is a polytope with $v^m$ vertices described by $mh$ inequalities and lives in $\mathbb R^{tm}$. $\endgroup$ Oct 27, 2022 at 16:31

1 Answer 1

1
$\begingroup$

I don't know whether I get you completely right.

But for sure you can position your $m$ polytopes within fully orthogonal spaces and consider the convex hull of that configuration, provided that the individual polytopes already had been convex.

Then the vertex count just is the sum of the vertex counts of the given $m$ individual polytopes and the restriction of the bounding hyperplanes of the total polytope to the according subspaces, where the individual given polytopes would live, are just the bounding hyperplanes of those polytopes.

Just consider the simple example of 2 orthogonally placed intervals of size $\sqrt2$, the hull of which provides a square… - The same holds for any number $m$ of components and any (convex) shape of components.

This, btw., is the way like crosspolytopes (aka orthoplexes) are constructed. You also can find some reference on that as the tegum product by W. Krieger (cf. tegum product)

--- rk

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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