  The Orbit Problem consists of determining, given a matrix $A\in
\mathbb{R}^{d\times d}$ and vectors $x,y\in \mathbb{R}^d$, whether there exists
$n\in \mathbb{N}$ such that $A^n=y$. This problem was shown to be decidable in
a seminal work of Kannan and Lipton in the 1980s. Subsequently, Kannan and
Lipton noted that the Orbit Problem becomes considerably harder when the target
$y$ is replaced with a subspace of $\mathbb{R}^d$. Recently, it was shown that
the problem is decidable for vector-space targets of dimension at most three,
followed by another development showing that the problem is in PSPACE for
polytope targets of dimension at most three. In this work, we take a dual look
at the problem, and consider the case where the initial vector $x$ is replaced
with a polytope $P_1$, and the target is a polytope $P_2$. Then, the question
is whether there exists $n\in \mathbb{N}$ such that $A^n P_1\cap P_2\neq
\emptyset$. We show that the problem can be decided in PSPACE for dimension at
most three. As in previous works, decidability in the case of higher dimensions
is left open, as the problem is known to be hard for long-standing
number-theoretic open problems.
  Our proof begins by formulating the problem as the satisfiability of a
parametrized family of sentences in the existential first-order theory of
real-closed fields. Then, after removing quantifiers, we are left with
instances of simultaneous positivity of sums of exponentials. Using techniques
from transcendental number theory, and separation bounds on algebraic numbers,
we are able to solve such instances in PSPACE.

Computational Complexity