# Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?

A number of geometric problems are easy when considered in $R^1$, but are NP-complete in $R^d$ for $d\geq2$ (including one of my favourite problems, unit disk cover).

Does anyone know of a problem which is polytime solvable for $R^1$ and $R^2$, but NP-complete for $R^d,d\geq3$?

More generally, do problems exist which are NP-complete for $R^k$ but polytime solvable for $R^{k-1}$, where $k\geq3$?

Set cover by half-spaces.

Given a set of points in the plane, and a set of halfplanes computing the minimum number of halfplanes covering the point sets can be solved in polynomial time in the plane. The problem however is NP hard in 3d (it is harder than finding a min cover by subset of disks of points in 2d). In 3d you are given a subset of halfspaces and points, and you are looking for min number of halfspaces covering the points.

The polytime algorithm in 2d is described here: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/

• I'm a bit embarrassed that I didn't know this result, given how close it is to the problems that I work on :-) This is also exactly the sort of answer I was hoping for. When you say that it's harder than disk cover in 2D, I guess you mean that it's APX-hard? – Bob Fraser Mar 3 '11 at 14:31
• The 2d problem is polynomial. The other one is NP-Hard. However, I dont think the 3d problem is APX hard. There are good reasons to believe a PTAS might be possible, via local search... – Sariel Har-Peled Mar 5 '11 at 16:23
• ...and by harder I meant that the disk problem can be lifted (i.e., reduced) to the halfspaces problem in 3d. – Sariel Har-Peled Mar 7 '11 at 2:52

It's not quite what you ask, because the 3d version is even harder than NP-complete, but: Finding a shortest path between two points among polygonal obstacles in the plane is in polynomial time (most simply, construct the visibility graph of the two terminals and the polygon vertices and apply Dijkstra; there is also a more complicated O(n log n) algorithm due to Hershberger and Suri, SIAM J. Comput. 1999) but finding a shortest path among polyhedral obstacles in 3d is PSPACE-complete (Canny and Reif, FOCS 1987).

• Are you sure about the planar case? The algorithms you cite fundamentally require exact real arithmetic! cstheory.stackexchange.com/questions/4034/… – Jeffε Mar 3 '11 at 4:55
• Er. Good point. And I can't get out of it by saying to use floating point and approximate, because the 3d problem can be well approximated. Oops. I guess there is an "exact real arithmetic" sense in which one is polynomial and the other is hard, but still, you're right, that's another way in which it doesn't answer the question. – David Eppstein Mar 3 '11 at 6:08
• This is really interesting. The sum of square roots problem creeps into a number of problems in cg where the problem would be easy except for this detail. It's great in a way, because it's one of these problems that you need to convince people that it's difficult. Thanks for the pointers. – Bob Fraser Mar 3 '11 at 14:08

Any non-convex polygon in the plane can be triangulated in O(n) time with no Steiner points; that is, every vertex of the triangulation is a vertex of the polygon. Moreover, every triangulation has exactly n-2 triangles.

However, determining whether a non-convex polyhedron in R^3 can be triangulated without Steiner points is NP-complete. The NP-hardness result holds even if you are given a triangulation with one Steiner point, so even approximating the minimum number of Steiner points required is NP-hard. [Jim Ruppert and Raimund Seidel. On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra. Discrete Comput. Geom. 1992.]

If the given polyhedron is convex, finding a triangulation is easy, but finding the triangulation with the minimum number of tetrahedra is NP-hard. [Alexander Below, Jesús de Loera, and Jürgen Richter-Gebert. The complexity of finding small triangulations of convex 3-polytopes. J. Algorithms 2004.]

• Thanks for the pointers, Jeff. In particular, I think that the last result that you mention is interesting. It's a bit surprising that while in the plane, the number of simplices which compose the polygon is a constant, but this no longer holds in higher dimensions and is in fact hard to optimize. This is exactly the sort of answer that I was hoping for. – Bob Fraser Mar 3 '11 at 14:23

The realizability problem for $d$-dimensional polytopes is a candidate. When $d \le 3$, it's polynomial-time solvable (by Steinitz' theorem), but when $d \ge 4$, this is NP-hard. For further information, please look at "Realization spaces of 4-polytopes are universal" by Richter-Gebert and Ziegler (there is an arxiv version as well), and the book "Lectures on Polytopes" (2nd printing) by Ziegler.

• More specifically than saying that it's NP-hard, it's complete for $\exists\mathbb{R}$, the existential theory of the real numbers. – David Eppstein Mar 3 '11 at 0:54
• I hadn't seen this problem before, thanks. – Bob Fraser Mar 3 '11 at 14:11
• Again, like David Eppstein's answer, harder (probably) than NP-complete. – Peter Shor Mar 3 '11 at 19:33

Deciding if a metric space is isometrically embeddable into R^2 is easy. However, it is NP-hard to decide for R^3 embeddability.

Embedding into $\ell_\infty^2$ is easy, embedding into $\ell_\infty^3$ is NP-complete. Jeff Edmonds. SODA 2007

Paper

• That's also a good example. – Suresh Venkat Nov 12 '11 at 5:01

This answer doesn't exactly answer your question, but it does have some smaller ties. Rather than answering for $R^2$ and $R^3$, I show you that this exists in $Z^2$ and $Z^3$.

The 2-SAT problem (Boolean Satisfiability) is solvable in polynomial time. Although it is not necessarily "geometric", there is a corresponding problem known as matching, which is more geometric, in a sense, and maps directly with the 2-SAT problem. The name matching is a more general version of k-dimensional matching, where $k = 2$. To reply to your question, the 3-SAT problem is NP-complete, which maps directly to the 3-dimensional matching problem, which also is NP-complete. Thus, the k-SAT problem (and thus the k-dimensional matching) is another problem that is tractable in $Z^2$ and is NP-complete in $Z^k$ where $k > 2$.

• what does it mean to say that 2SAT is "in" R^2 ? – Suresh Venkat Mar 3 '11 at 0:06
• @Suresh 2-satisfiability (abbreviated as 2-SAT or just 2SAT) is the problem of determining whether a collection of two-valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all the constraints. (That's from Wikipedia) Because it is a problem solved for a set of 2-valued variables, the variables can be thought of as begin "in" $R^2$. – Kaushik Shankar Mar 3 '11 at 0:09
• -1: I don't see how 2SAT is in R^2. I don't see how 2SAT is a "geometric problem." – Robin Kothari Mar 3 '11 at 0:34
• I apologize for not presenting a geometric problem, but although the title asks about geometric problems, the two questions within the comments don't specify it being geometric. Furthermore, 2-satisfiability has a graph representation known as 2-dimensional matching, that is in P, where as the 3-satisfiability corresponds with 3-dimensional matching, which is NP. – Kaushik Shankar Mar 3 '11 at 1:17
• @Robin I went ahead and clarified in my original comment. – Kaushik Shankar Mar 3 '11 at 1:36