  For a polyhedron $P$ in $\mathbb{R}^d$, denote by $|P|$ its combinatorial
complexity, i.e., the number of faces of all dimensions of the polyhedra. In
this paper, we revisit the classic problem of preprocessing polyhedra
independently so that given two preprocessed polyhedra $P$ and $Q$ in
$\mathbb{R}^d$, each translated and rotated, their intersection can be tested
rapidly.
  For $d=3$ we show how to perform such a test in $O(\log |P| + \log |Q|)$ time
after linear preprocessing time and space. This running time is the best
possible and improves upon the last best known query time of $O(\log|P|
\log|Q|)$ by Dobkin and Kirkpatrick (1990).
  We then generalize our method to any constant dimension $d$, achieving the
same optimal $O(\log |P| + \log |Q|)$ query time using a representation of size
$O(|P|^{\lfloor d/2\rfloor + \varepsilon})$ for any $\varepsilon>0$ arbitrarily
small. This answers an even older question posed by Dobkin and Kirkpatrick 30
years ago.
  In addition, we provide an alternative $O(\log |P| + \log |Q|)$ algorithm to
test the intersection of two convex polygons $P$ and $Q$ in the plane.
