Erdős-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3 dimensions - and what now?

Details Erdős-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3 dimensions - and what now? Erdős-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3 dimensions - and what now?

2011-11-25

arxiv.org/abs/1111.5979v1

Computer Science

Computational Geometry

6 pages, no figures

Scientific paper

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 R^3. 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.

Affiliated with

Also associated with

No associations

Rating

Erdős-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3 dimensions - and what now? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Erdős-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3 dimensions - and what now?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Erdős-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3 dimensions - and what now? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-174310