General Mathematics


Erd ̋os-Szekeres is NP-Hard in 3 Dimensions and What Now?

Authors: Thinh Nguyen

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. These questions have also been studied extensively from a computational point of view, and polynomial time algorithms for finding the largest (empty) convex set have been given for the planar case. In higher dimension, it is not known how to compute such a set efficiently. In this paper, we show that already in 3 dimensions no polynomial time algorithm exists for determining the largest (empty) convex set (unless $P$=$NP$), 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 $ε$-nets in $R^3$ . Answering a question by Chazelle et al. from 1995, our reduction shows that the problem is $co-NP$-hard. Finally, we make several suggestions for further research on the subject.

Comments: 4 Pages.

Download: PDF

Submission history

[v1] 2018-07-03 06:11:19

Unique-IP document downloads: 0 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus