convex-analysisconvex-geometrypolytopes
Let $K=\operatorname{conv}(x_1,,…,x_n)\subset\mathbb R^n$ be a convex polytope. Its polar set is defined as
$$K^\circ\equiv\{x\in\mathbb R^n : \langle x,y\rangle\le 1\forall y\in K\}.$$
We know that $K^\circ$ is always convex, and moreover that when $K$ is a polytope, $K^\circ$ is a polytope.
A few examples of polar sets in $\mathbb R^2$ are given in this answer.
Is there a good/efficient/elegant way to write the vertices of $K^\circ$, given the vertices of $K$?
Answer to the Revised Question. Indeed, the union $P = \cup_{\mathbf{q}} A(\mathbf{q})$ is a polytope. To show this, let
$$ \tilde{P} = \texttt{ConvexHull}(\cup_{i=1}^{m} A(\mathbf{e}_i))$$
where $\mathbf{e}_1, \ldots, \mathbf{e}_m$ are the standard basis vectors of $\mathbb{R}^m$. Since $\tilde{P}$ is the convex hull of a finite union of polytopes, $\tilde{P}$ itself is also a polytope (which is spanned by the union of vertices of $A(\mathbf{e}_i)$'s.)
Claim. $P = \tilde{P}$.
Proof. Since $P$ is a convex set containing each of $A(\mathbf{e}_i)$, it is clear that $\tilde{P} \subseteq P$. So it suffices to prove that $P \subseteq \tilde{P}$.
To this end, let $\mathbf{x} \in P$ be arbitrary. Then there exists a probability vector $\mathbf{q}$ such that $\mathbf{x} \in A(\mathbf{q})$. To show that $\mathbf{x} \in \tilde{P}$, it suffices to show that there exist $\mathbf{x}^{(i)} \in A(\mathbf{e}_i)$, $i = 1, \ldots, m$, such that
$$ \mathbf{x} = q_1 \mathbf{x}^{(1)} + \cdots + q_m \mathbf{x}^{(m)}. \tag{*} $$
To this end, we note:
\begin{align*} \mathbf{x} \in A(\mathbf{q}) &\iff x_j = c_{j} \langle \mathbf{y}(j), \mathbf{q} \rangle \quad \text{for some $c_1, \ldots, c_n \in [0, 1]$} \\ &\implies x_j = \sum_{i=1}^{m} q_i c_{j} \langle \mathbf{y}(j), \mathbf{e}_i \rangle \quad \text{for some $c_1, \ldots, c_n \in [0, 1]$}. \end{align*}
So, if we set $\mathbf{x}^{(i)} = \sum_{j=1}^{n} c_{j} \langle \mathbf{y}(j), \mathbf{e}_i \rangle \mathbf{e}_j$, then $\mathbf{x}^{(i)} \in A(\mathbf{e}_i)$ for each $i$ and $\text{(*)}$ holds, concluding the desired claim. $\square$
Answer to the Original Question. If some of the hypercubes are allowed to be not "parallel" to one another, then there is a counter-example.
Let me construct a counter-example in 2D case. We begin by noting the following observation:
Lemma. Every polygon in $\mathbb{R}^2$ with no acute interior angles can be written as a finite union of squares.
Since its proof is not so fun to write down rigorously, let me provide an animated illustration of how the proof works:
In light of this lemma, we may weaken the condition on $A(i)$'s by allowing them to be polygons with no acute interior angles. Now we are ready to construct a counter-example:
Set $P_1 = (0, 1)$, $P_2 = (-1, 0)$, $P_3 = (0, -1)$, and $Q_k = (\sin(\pi/2k), \cos(\pi/2k))$ for $k = 1, 2, 3, \ldots$
For each $i$, let $A(i)$ be the polygon with vertices $P_1, P_2, P_3, Q_1, \ldots, Q_i$.
Then $\cup_{i=1}^{\infty} A(i)$ is the compact convex hull spanned by $P_1, P_2, P_3, Q_1, Q_2, \ldots$, which is clearly not a polygon:
Best Answer
In principle, you have have to do the following:
The dual polytope can also be given as the set
$$P^\circ =\{x\in\Bbb R^d\mid \langle x, x_i\rangle\le 1 \text{ for all $i=1,...,n$}\}.$$
Each vertex of $P^\circ$ is the intersection of hyperplanes $\langle x,x_i\rangle =1$ for all $i\in I$ for some subset $I\subseteq \{1,...,n\}$. You would have to compute all these $\approx 2^n$ intersections $v_I\in\Bbb R^d,I\subset\{1,...,n\}$ to find all the "potential vertices" (you can be a bit clever here, but it stays $\mathcal O(2^{n/2})$). That is
$$P^\circ=\mathrm{conv}\{v_I\mid I\subseteq\{1,...,n\}\}.$$
Then you have to check which of these are actual vertices, because some $v_I$ might violate an inequality $\langle x,x_i\rangle\le 1$ for some $i\not\in I$.
I suppose there are much more clever ways to do the details, but the core idea is the one above. Also this will never happen in polynomial time.