DocumentCode
2115362
Title
On the measure of two-dimensional regions with polynomial-time computable boundaries
Author
Ko, Ker-I ; Weihrauch, Klaus
Author_Institution
Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA
fYear
1996
fDate
24-27 May 1996
Firstpage
150
Lastpage
159
Abstract
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
Keywords
Turing machines; computability; computational complexity; Lebesgue measure; computability; interior region; polynomial-time computable; polynomial-time computable boundary; two-dimensional region; Computational geometry; Computer science; Polynomials; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
Conference_Location
Philadelphia, PA
Print_ISBN
0-8186-7386-9
Type
conf
DOI
10.1109/CCC.1996.507677
Filename
507677
Link To Document