Finding minimal convex nested polygons

We consider the problem of finding a polygon nested between two given convex polygons that has a minimal number of vertices. Our main result is an O(nlogfc) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and k is the number of vertices of a minimal nested polygon. We also present an 0(n) sub-optimal algorithm, and a simple 0(nk) optimal algorithm.