Search

The problem of finding a piecewise straight-line path, with a constant number of line segments, in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. It is proved that, for polynomial-time recognizable domains associated with polynomial-time computable distance functions, the complexity of this problem is equivalent to a discrete problem which is complete for ∑2P, the second level of the polynomial-time hierarchy.

We investigate the computational complexity of computing the convex hull of a two-dimensional set. We study this problem in the polynomial-time complexity theory of real functions based on the oracle Turing machine model. We show that the convex hull of a two-dimensional Jordan domain S is not necessarily recursively recognizable even if S is polynomial-time recognizable. On the other hand, if the boundary of a Jordan domain S is polynomial-time computable, then the convex hull of S must be NP-recognizable, and it is not necessarily polynomial-time recognizable if P≠NP. We also show that the area of the convex hull of a Jordan domain S with a polynomial-time computable boundary can be computed in polynomial time relative to an oracle function in #P. On the other hand, whether the area itself is a #P real number depends on the open question of whether NP=UP.