An Optimal Algorithm for the Separating Common Tangents of Two Polygons

摘要

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 lin