A fast modification of Focke's shortest inpolygon construction
Günter Deweß, P. Helbig · Optimization · 1991
We want to find an inpolygon of shortest circumference in a given convex polygon with m vertices. Focke [2] evolves the polygon under successive reflection, lays a line corresponding to an inpolygon through all concave vertices of this “channel” and shortens the line by a descent method with complexity O(m 3) to an optimum. We determine a first active vertex of the channel with complexity O(m) lay a straight line through this vertex and lengthen the line by a trivial method with complexity O(m 2) to a feasible line (optimum).