Computational complexity of two-dimensional regions

The computational complexity of bounded sets of the two-dimensional plane is studied in the discrete computational model. We introduce four notions of polynomial-time computable sets in R 2 and study their relationship. The computational complexity of the winding number problem, the membership problem, the distance problem and the area problem is characterized by the relations between discrete complexity classes of the NP theory.