On the computational complexity of Erd"os-Szekeres and related problems in R^3
Presented by Dr. Panos GIANNOPOULOS
Type: Oral presentation
Track: Discrete and Computational Geometry
The Erd"os-Szekeres theorem states that, for every k, there is a number n_k such that every set of n_k points in general position in the plane contains a subset of k points in convex position. If we ask the same question for subsets whose convex hull does not contain any other point from the set, this is not true: as shown by Horton, there are sets of arbitrary size that do not contain an empty 7-gon. We will discuss computational aspects of these problems. In particular, while it is known that computing a maximum size subset in (empty) convex position in R^2 is in P, both problems becomes NP-hard in R^3. Also, while deciding whether there exists a k-subset in convex position in R^3 is trivially fixed-parameter tractable (due to the The Erd"os-Szekeres theorem itself), the problem becomes W-hard when emptiness and strict convexity conditions are imposed.