Jordan curves with polynomial inverse moduli of continuity
- 作者：Ker-I Ko ; Fuxiang Yu
- 关键词：Computational complexity of real functions ; Jordan curve ; Polynomial inverse modulus of continuity ; none ; color ; black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6V1G-4NJ20K3-2&_mathId=mml5&_user=10&_cdi
- 刊名：Theoretical Computer Science
- 出版年：2007
- 期刊代码：114_03043975
- 类别：cp
- 出版时间：22 August 2007
- 卷：381
- 期：1-3
- 页码：148-161
- 文件大小：638 K
摘要
Computational complexity of two-dimensional domains whose boundaries are polynomial-time computable Jordan curves with polynomial inverse moduli of continuity is studied. It is shown that the membership problem of such a domain can be solved in 
, i.e., in polynomial time relative to an oracle in 
, in contrast to the higher upper bound 
for domains without the property of polynomial inverse modulus of continuity. On the other hand, the lower bound of 
for the membership problem still holds for domains with polynomial inverse moduli of continuity. It is also shown that the shortest path problem of such a domain can be solved in PSPACE, close to its known lower bound, while no fixed upper bound was known for domains without this property.