On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain (Q864430)

Complexity of finding, from a given polynomial-time computable Jordan curve, the circumscribed rectangles and squares of minimum area is studied [cf. \textit{K.-I. Ko} and \textit{H. Friedman}, Theoret. Comput. Sci. 20, 323--352 (1982; Zbl 0498.03047)]. Results similar to a general minimization problem are obtained. In particular, it is shown that the problem of finding the minimum area of circumscribed rectangle of a polynomial-time computable Jordan curve is equivalent to a discrete \(\Sigma _2^P\)-complete problem.