Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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/
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).
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.]
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.
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
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$.
