Hausdorff Core of a One Reflex Vertex Polygon
Robert Fraser, Patrick K. Nicholson · 2010
In this paper we present a polynomial time algorithm for computing a Hausdorff core of a polygon with a single reflex vertex. A Hausdorff core of a polygon P is a convex polygon Q contained inside P which minimizes the Hausdorff distance between P and Q. Our algorithm essentially consists of rotating a line about the reflex vertex; this line defines a convex polygon by cutting P. To determine the angle at which the line should be rotated, our algorithm searches for a global minimum on the upper envelope of n continuous piecewise functions, where n is the number of vertices of P. 1