On separating two simple polygons by a single translation

Let P and Q be two disjoint simple polygons having n sides each. We present an algorithm which determines whether Q can be moved by a single translation to a position sufficiently far from P, and which produces all such motions if they exist. The algorithm runs in time O(t(n)) where t(n) is the time needed to triangulate an n-sided polygon. Since Tarjan and Van Wyk have recently shown that t(n)=O(n log log n) this improves the previous best result for this problem which was O(n log n) even after triangulation.