Jordan Curves with Polynomial Inverse Moduli of Continuity | Zendy

KerI Ko | Zendy; Fuxiang Yu | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Jordan Curves with Polynomial Inverse Moduli of Continuity

Author(s) -

KerI Ko,

Fuxiang Yu

Publication year - 2007

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2006.08.022

Subject(s) - mathematics , upper and lower bounds , inverse , polynomial , pspace , time complexity , domain (mathematical analysis) , combinatorics , discrete mathematics , mathematical analysis , pure mathematics , computational complexity theory , geometry , algorithm

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 PNP, i.e., in polynomial time relative to an oracle in NP, in contrast to the higher upper bound PMP for domains without the property of polynomial inverse modulus of continuity. On the other hand, the lower bound of UP for the membership problem still holds for domains with polynomial inverse moduli of continuity. It is also shown that the path problem of such a domain can be solved in PSPACE, matching its known lower bound, while no fixed upper bound was known for domains without this property

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research