I recently stumbled upon the following subproblem: we are given zonotopes $P_1, \dots, P_m$ in $\mathcal{V}$ representation (i.e. we are given the extreme points of each $P_i$). Denote the Minkowski sum
$$ P \oplus Q := \{p + q : p \in P, q \in Q\} $$
In the setting I'm interested in, we want to count the vertices of $(P_1 \oplus \dots \oplus P_m)$.
Problem: Is there an $O(n)$ randomized algorithm that approximately counts the extreme points of $P_1 \oplus \dots \oplus P_m$ with high (or constant) probability, where $n$ is the total number of extreme points?
I'm aware of the existence of deterministic algorithms for vertex enumeration, however these usually involve solving $n$ linear programs. I'm looking for something simpler, e.g. a random projection method or something similar that gives us a nontrivial lower bound on the number of $n$.