P-COMPLETE GEOMETRIC PROBLEMS
Mikhail J. Atallah, Paul B. Callahan, Michael T. Goodrich · International Journal of Computational Geometry & Applications · 1993
In this paper we show that it is impossible to solve a number of “natural” two-dimensional geometric problems in polylog time with a polynomial number of processors (unless P=NC). Thus, we disprove a popular belief that there are no natural P-complete geometric problems in the plane. The problems we address include instances of polygon triangulation, planar partitioning, and geometric layering. Our results are based on non-trivial reductions from the monotone circuit value and planar circuit value problems.