On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain (Q864430)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain |
scientific article; zbMATH DE number 5123556
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain |
scientific article; zbMATH DE number 5123556 |
Statements
On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain (English)
0 references
8 February 2007
0 references
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.
0 references
computational complexity
0 references
circumscribed rectangles
0 references
complexity
0 references
polynomial-time computable Jordan curve
0 references
minimum area
0 references
