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?
$\begingroup$
$\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$– Joseph O'RourkeCommented Apr 22, 2019 at 23:28
-
$\begingroup$ @JosephO'Rourke Yes second. However I think only if is might not be possible. $\endgroup$– VS.Commented 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$– Francisco SantosCommented Oct 27, 2022 at 16:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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
answered Jun 8, 2019 at 11:47