Computational Complexity of Two-Dimensional Regions
Arthur W. Chou, Ker‐I Ko · SIAM Journal on Computing · 1995
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 ${\bf R}^{2}$ and study their relationship. The computational complexity of the winding number problem, membership problem, distance problem, and area problem is characterized by the relations between discrete complexity classes of the NP theory.