کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
422161 | 685035 | 2008 | 15 صفحه PDF | دانلود رایگان |

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.
Journal: Electronic Notes in Theoretical Computer Science - Volume 202, 21 March 2008, Pages 121-135