COMPUTING THE INTERSECTION-DEPTH OF POLYHEDRA

Given two intersecting polyhedra P, Q and a direction d, find the smal lest translation of Q along d that renders the interiors of P and Q di sjoint. The same problem can also be posed without specifying the dire ction, in which case the minimum translation over all directions is so ught. These are fundamental problems that arise in robotics and comput er vision. We develop techniques for implicitly building and searching convolutions and apply them to derive efficient algorithms for these problems.