The orthogonal convex skull problem

We give a combinatorial definition of the notion of a simple orthogonal polygon beingk-concave, wherek is a nonnegative integer. (A polygon is orthogonal if its edges are only horizontal or vertical.) Under this definition an orthogonal polygon which is 0-concave is convex, that is, it is a rectangle, and one that is 1-concave is orthoconvex in the usual sense, and vice versa. Then we consider the problem of computing an orthoconvex orthogonal polygon of maximal area contained in a simple orthogonal polygon. This is the orthogonal version of the potato peeling problem. AnO(n²) algorithm is presented, which is a substantial improvement over theO(n⁷) time algorithm for the general problem.The work of the first author was supported under a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692 and the work of the second author was partially supported by NSF Grants Nos. DCR-84-01898 and DCR-84-01633.