Modification of Melkman's algorithm for the convex hull

Question

I am using Melkman's algorithm for the convex hull of simple polygons, which is a gem.

In addition to the convex hull itself, I need to know what are the contact points, i.e. the vertices that are the endpoints of edges that were not in the original polygon (red points/blue edges in the figure).

I can find these points by comparing the initial polygon to the convex hull in linear time, but I was wondering if a simple modification of Melkman's algorithm could produce these points as a byproduct.

Answer 1

Save the indices of the vertices, not the points.

Green edges correspond to consecutive indices. Blue bridges correspond to jumps.

Take care to handle $n \to 1$ as green.