COMPUTATIONAL-COMPLEXITY OF 2-DIMENSIONAL REGIONS

Authors
CHOU AW KO KI
Citation
Aw. Chou et Ki. Ko, COMPUTATIONAL-COMPLEXITY OF 2-DIMENSIONAL REGIONS, SIAM journal on computing, 24(5), 1995, pp. 923-947
Citations number
20
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
24
Issue
5
Year of publication
1995
Pages
923 - 947
Database
ISI
SICI code
0097-5397(1995)24:5<923:CO2R>2.0.ZU;2-R
Abstract
The computational complexity of bounded sets of the two-dimensional pl ane is studied in the discrete computational model. We introduce four notions of polynomial-time computable sets in R(2) and study their rel ationship. The computational complexity of the winding number problem, membership problem, distance problem, and area problem is characteriz ed by the relations between discrete complexity classes of the NP theo ry.