# Modification of Melkman's algorithm for the convex hull

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.

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