Consider a non-empty, bounded $\mathcal H$-polyhedron described by
$$P = \left\{ x \in \mathbb{R}^n : Ax \leq b \right\}$$
Is there an algorithm to determine the minimum distance (in the $\ell_1$, $\ell_2$ or $\ell_\infty$ sense, say) between two distinct vertices of $P$ without converting it to its vertex representation?
What about a good (non-trivial) lower bound on the minimum distance instead?
More generally, suppose I'm also given another non-empty, bounded $\mathcal H$-polyhedron
$$Q = \left\{x \in \mathbb{R}^n: Cx \leq d\right\}$$
such that $P \cap Q$ may be non-empty. What is (a lower bound to) the minimum distance between a vertex $p$ of $P$ and a vertex $q$ of $Q$ such that $p \neq q$?
Assuming that the inequalities are linearly independent, $x \in \mathbb{R}^n$ is a vertex if and only if $Ax \leq b$ and $a_i^Tx = b_i$ for $n$ (out of $m$) inequalities (the equivalence between a vertex and a basic feasible solution is well known). Let $L_i$ be a lower bound of $a_i^T x$ over the polyhedron. The set of vertices can be represented as: $$\{ x \in \mathbb{R}^n : L_i + (b_i-L_i)y_i\leq a_i^T x \leq b_i \; (i=1,\ldots,m), \sum_i y_i=n, y \in \{0,1\}^m \}.$$ For the second vertex you get: $$\{ x' \in \mathbb{R}^n : L'_i + (d_i-L'_i)y'_i\leq c_i^T x' \leq d_i \; (i=1,\ldots,m'), \sum_i y'_i=n, y' \in \{0,1\}^m \}.$$ The $\ell_1$ and $\ell_\infty$ norm can be represented in linear optimization. This gives rise to a mixed integer linear optimization problem. Solvers for such problems (such as cplex) often find the optimum or provide meaningful bounds. You will get better results if you use the strongest lower bound for $L_i$, which can be computed via linear programming: $\min \{ a_i^T x : Ax \leq b\}$.
The only challenge now is to add a constraint that two vertices are distinct. Maybe it is sufficient to have $y \neq y'$. One way to do this is to add the following linear constraints: $$\{1-z_i \leq y_i+y'_i \leq 1+z_i, \sum_i z_i \leq m-1, z \in \{0,1\}^m\}.$$
Combining everything, for the $\ell_1$ norm, you get: $$\begin{align}\min \quad &\sum_i w_i \\ \text{s.t.}\quad & -w \leq x-x' \leq w \\ & L_i + (b_i-L_i)y_i\leq a_i^T x \leq b_i \; (i=1,\ldots,m) \\ &L'_i + (d_i-L'_i)y'_i\leq c_i^T x' \leq d_i \; (i=1,\ldots,m') \\ &\sum_i y_i=n \\ &\sum_i y'_i=n \\ & 1-z_i \leq y_i+y'_i \leq 1+z_i \; (i=1,\ldots,m') \\ &\sum_i z_i \leq m-1 \\ &w \in \mathbb{R}^n, x \in \mathbb{R}^n, x' \in \mathbb{R}^n, y \in \{0,1\}^m, y' \in \{0,1\}^m, z \in \{0,1\}^m \end{align}$$ Suppose the solution $(\hat{y},\hat{y}')$ is invalid you can add a cut to invalidate that solution: $$\sum_{i=1}^m (1-y_i) 1_{\hat{y}_i=1} + y_i 1_{\hat{y}_i=0} + \sum_{i=1}^{m'} (1-y'_i) 1_{\hat{y}'_i=1} + y'_i 1_{\hat{y}'_i=0} \geq 1.$$