On the computational complexity of the Riemann mapping

Ilia Binder; Mark Braverman; Michael Yampolsky

doi:10.1007/s11512-007-0045-x

On the computational complexity of the Riemann mapping

Ilia Binder, Mark Braverman, Michael Yampolsky

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

Abstract

In this paper we consider the computational complexity of uniformizing a domain with a given computable boundary. We give nontrivial upper and lower bounds in two settings: when the approximation of the boundary is given either as a list of pixels, or by a Turing machine.

Original language	English (US)
Pages (from-to)	221-239
Number of pages	19
Journal	Arkiv for Matematik
Volume	45
Issue number	2
DOIs	https://doi.org/10.1007/s11512-007-0045-x
State	Published - Oct 2007
Externally published	Yes

All Science Journal Classification (ASJC) codes

Mathematics(all)

Access to Document

10.1007/s11512-007-0045-x

Cite this

@article{3085775fd3c9485fbd08115e9742a93e,

title = "On the computational complexity of the Riemann mapping",

abstract = "In this paper we consider the computational complexity of uniformizing a domain with a given computable boundary. We give nontrivial upper and lower bounds in two settings: when the approximation of the boundary is given either as a list of pixels, or by a Turing machine.",

author = "Ilia Binder and Mark Braverman and Michael Yampolsky",

note = "Funding Information: Acknowledgements. The second author would like to thank Ker-I Ko for bringing the problem to his attention during CCA{\textquoteright}04. The authors are grateful to Stephen Cook for his numerous helpful suggestions during the preparation of the paper.",

year = "2007",

month = oct,

doi = "10.1007/s11512-007-0045-x",

language = "English (US)",

volume = "45",

pages = "221--239",

journal = "Arkiv for Matematik",

issn = "0004-2080",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - On the computational complexity of the Riemann mapping

AU - Binder, Ilia

AU - Braverman, Mark

AU - Yampolsky, Michael

N1 - Funding Information: Acknowledgements. The second author would like to thank Ker-I Ko for bringing the problem to his attention during CCA’04. The authors are grateful to Stephen Cook for his numerous helpful suggestions during the preparation of the paper.

PY - 2007/10

Y1 - 2007/10

N2 - In this paper we consider the computational complexity of uniformizing a domain with a given computable boundary. We give nontrivial upper and lower bounds in two settings: when the approximation of the boundary is given either as a list of pixels, or by a Turing machine.

AB - In this paper we consider the computational complexity of uniformizing a domain with a given computable boundary. We give nontrivial upper and lower bounds in two settings: when the approximation of the boundary is given either as a list of pixels, or by a Turing machine.

UR - http://www.scopus.com/inward/record.url?scp=38049009611&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38049009611&partnerID=8YFLogxK

U2 - 10.1007/s11512-007-0045-x

DO - 10.1007/s11512-007-0045-x

M3 - Article

AN - SCOPUS:38049009611

SN - 0004-2080

VL - 45

SP - 221

EP - 239

JO - Arkiv for Matematik

JF - Arkiv for Matematik

IS - 2

ER -

On the computational complexity of the Riemann mapping

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this