Name
Abstract | ||
|---|---|---|
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 PNP. 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.entcs.2008.03.012 | Electr. Notes Theor. Comput. Sci. |
Keywords | Field | DocType |
convex hulls,convex hull,polynomial-time computable,two-dimensional set,polynomial-time complexity theory,np,oracle turing machine model,oracle function,p real number,polynomial-time computable boundary,jordan domain,two-dimensional plane,polynomial time,two-dimensional jordan domain,computational complexity,turing machine | Orthogonal convex hull,Discrete mathematics,Combinatorics,Convex combination,Effective domain,Convex set,Convex hull,Convex polytope,Proper convex function,Convex analysis,Mathematics | Journal |
Volume | ISSN | Citations |
202, | Electronic Notes in Theoretical Computer Science | 3 |
PageRank | References | Authors |
0.45 | 12 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ker-I Ko | 1 | 196 | 28.54 |
| Fuxiang Yu | 2 | 19 | 4.83 |