Luis Barba

For a polyhedron *P* in ℝ^{d}, denote by |*P*| its combinatorial complexity, i.e., the number of faces, edges and vertices of the polyhedra.
In this talk, we revisit the classic problem of preprocessing
polyhedra independently so that given two preprocessed polyhedra *P*
and *Q* in ℝ^{d}, each arbitrarily 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 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
O(log |*P*| + log |*Q*|) query time using a representation of size
O(|*P*|^{⌊d/2⌋+ε}) for any ε>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.