Computing a convex skill of an orthogonal polygon
Derick Wood, Chee Keng Yap · 1985
Given a simple orthogonal polygon, that is a simple polygon whose edges are parallel to the axes, we wish to determine an inscribed convex orthogonal polygon of maximal area. This is the orthogonal version of the potato peeling problem. We present an Ο(n2) time algorithm to solve it, which is a substantial improvement over the Ο(n7 time algorithm for the general problem.