2011/11/25 by Christian Knauer, Knauer, Christian, Daniel Werner +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.CC #cs.CG
paper · pdf · doi:10.48550/arxiv.1111.5979
6 pages, no figures
arxiv created 2011/11/25 · openalex publication_date 2011/11/25 · arxiv updated 2011/11/28 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
We consider the computational versions of the Erd\H os-Szekeres theorem and related problems in 3 dimensions. We show that, in constrast to the planar case, no polynomial time algorithm exists for determining the largest (empty) convex subset (unless P=NP) among a set of points, by proving that the corresponding decision problem is NP-hard. This answers a question by Dobkin, Edelsbrunner and Overmars from 1990. As a corollary, we derive a similar result for the closely related problem of testing weak epsilon-nets in R3. Answering a question by Chazelle et al. from 1995, our reduction shows that the problem is co-NP-hard. This is work in progress - we are still trying to find a smart approximation algorithm for the problems.