  We describe an algorithm for computing the separating common tangents of two
simple polygons using linear time and only constant workspace. A tangent of a
polygon is a line touching the polygon such that all of the polygon lies to the
same side of the line. A separating common tangent of two polygons is a tangent
of both polygons where the polygons are lying on different sides of the
tangent. Each polygon is given as a read-only array of its corners. If a
separating common tangent does not exist, the algorithm reports that.
Otherwise, two corners defining a separating common tangent are returned. The
algorithm is simple and implies an optimal algorithm for deciding if the convex
hulls of two polygons are disjoint or not. This was not known to be possible in
linear time and constant workspace prior to this paper.
  An outer common tangent is a tangent of both polygons where the polygons are
on the same side of the tangent. In the case where the convex hulls of the
polygons are disjoint, we give an algorithm for computing the outer common
tangents in linear time using constant workspace.
