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

DOI10.1016/J.JCO.2006.05.005MaRDI QIDQ864430zbMATH OpenOpenAlexFDO

Authors Fuxiang Yu, Arthur W. Chou, Ker-I Ko

Publication date 8 February 2007

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2006.05.005

zbMATH Keywords

circumscribed rectanglescomplexitycomputational complexityminimum areapolynomial-time computable Jordan curve

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4098747
• Jordan curves with polynomial inverse moduli of continuity
• Jordan curves with polynomial inverse moduli of continuity
• On the complexity of finding paths in a two-dimensional domain I: Shortest paths
• Computational Complexity of Two-Dimensional Regions

Cites work

• Computational complexity of real functions
• Computational Complexity of Two-Dimensional Regions
• Computing and Combinatorics
• Computing the width of a set
• Determining the minimum-area encasing rectangle for an arbitrary closed curve
• scientific article; zbMATH DE number 3143695 (Why is no real title available?)
• scientific article; zbMATH DE number 42077 (Why is no real title available?)
• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• Non-computable Julia sets
• On the complexity of finding paths in a two-dimensional domain I: Shortest paths
• The computational complexity of some Julia sets

Cited in

(3)

• Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length
• In Memoriam: Ker-I Ko (1950–2018)
• Who asked us? How the theory of computing answers questions about analysis

Describes a project that uses

Uses Software

• GTEngine

This page was built for publication: On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q864430)