On the measure of two-dimensional regions with polynomial-time computable boundaries
Ker‐I Ko, Klaus Weihrauch · 2002
We study the computability of the Lebesgue measure of a two-dimensional region that has a polynomial-time computable boundary. It is shown that the two-dimensional measure of the boundary itself completely characterizes the computability of the measure of the interior region. Namely, if a polynomial-time computable, simple, closed curve has measure zero, then its interior region must have a computable measure. Conversely, if such a curve has a positive measure, then the measure of its interior region could be any positive, left r.e. real number.