On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane

DOI10.1016/j.entcs.2008.03.012zbMath1262.03083OpenAlexW2036455597MaRDI QIDQ4918034

Fuxiang Yu, Ker-I. Ko

Publication date: 3 May 2013

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.entcs.2008.03.012

zbMATH Keywords

computational complexitypolynomial timeconvex hullsNPtwo-dimensional set

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Convex sets without dimension restrictions (aspects of convex geometry) (52A05) Computation over the reals, computable analysis (03D78)

Related Items (4)

On parallel complexity of analytic functions ⋮ On the computational complexity of the Dirichlet Problem for Poisson's Equation ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Jordan Areas and Grids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The computational complexity of distance functions of two-dimensional domains
• The complexity of computing the permanent
• On the complexity of computing the logarithm and square root functions on a complex domain
• The computational complexity of maximization and integration
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• On the complexity of finding paths in a two-dimensional domain I: Shortest paths
• PP is as Hard as the Polynomial-Time Hierarchy
• The computational complexity of some julia sets
• Computational Complexity of Two-Dimensional Regions
• Non-computable Julia sets

This page was built for publication: On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane