<p>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).</p>

CC BY-SA 2.5
2011-03-03T04:55:39.697Z
Are you sure about the planar case?  The algorithms you cite fundamentally require exact real arithmetic!  http://cstheory.stackexchange.com/questions/4034/complexity-of-computing-shortest-paths-in-the-plane-with-polygonal-obstacles
Jeffε
CC BY-SA 2.5
2011-03-03T06:08:11.813Z
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
CC BY-SA 2.5
2011-03-03T14:08:57.640Z
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
CC BY-SA 2.5
2011-03-02T19:23:33.753Z
2011-03-02T19:23:33.753Z
David Eppstein
<p>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.</p>

<p>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 <em>one</em> 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.  <em>Discrete Comput. Geom.</em> 1992.]</p>

<p>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.  <a href="http://arxiv.org/abs/math/0012177">The complexity of finding small triangulations of convex 3-polytopes</a>.  <em>J. Algorithms</em> 2004.]</p>

CC BY-SA 2.5
2011-03-03T14:23:21.590Z
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
CC BY-SA 2.5
2011-03-03T04:55:50.400Z
2011-03-03T04:55:50.400Z
Jeffε
<p>The realizability problem for $d$-dimensional polytopes is a candidate.  When $d \le 3$, it's polynomial-time solvable (by <a href="http://en.wikipedia.org/wiki/Steinitz%27s_theorem">Steinitz' theorem</a>), but when $d \ge 4$, this is NP-hard.  For further information, please look at "<a href="http://dx.doi.org/10.1090/S0273-0979-1995-00604-X">Realization spaces of 4-polytopes are universal</a>" by Richter-Gebert and Ziegler (there is <a href="http://arxiv.org/abs/math/9510217">an arxiv version</a> as well), and the book "<a href="http://www.springer.com/mathematics/geometry/book/978-0-387-94365-7">Lectures on Polytopes</a>" (2nd printing) by Ziegler.</p>

CC BY-SA 2.5
2011-03-03T00:54:49.273Z
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
CC BY-SA 2.5
2011-03-03T14:11:39.917Z
I hadn't seen this problem before, thanks.
Bob Fraser
CC BY-SA 2.5
2011-03-03T19:33:38.520Z
Again, like David Eppstein's answer, harder (probably) than NP-complete.
Peter Shor 
CC BY-SA 2.5
2011-03-03T00:39:23.497Z
2011-03-03T00:39:23.497Z
Yoshio Okamoto
<p>Deciding if a metric space is isometrically embeddable into R^2 is easy. However, it is NP-hard to decide for R^3 embeddability.</p>

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

<p><a href="http://dl.acm.org/citation.cfm?id=1283439">Paper</a></p>

CC BY-SA 3.0
2011-11-12T05:01:46.817Z
That's also a good example.
Suresh Venkat
CC BY-SA 3.0
2011-11-12T03:20:03.243Z
2011-11-12T03:20:03.243Z
Zouzias
<p>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$.</p>

<p>The 2-SAT problem (Boolean Satisfiability) is solvable in polynomial time. Although it is not necessarily "geometric", there is a corresponding problem known as <a href="http://en.wikipedia.org/wiki/Matching_%28graph_theory%29" rel="nofollow">matching</a>, which is more geometric, in a sense, and maps directly with the 2-SAT problem. The name matching is a more general version of <a href="http://en.wikipedia.org/wiki/3-dimensional_matching" rel="nofollow">k-dimensional matching</a>, 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 &gt; 2$.</p>

CC BY-SA 2.5
2011-03-03T00:06:30.530Z
what does it mean to say that 2SAT is "in" R^2 ?
Suresh Venkat
CC BY-SA 2.5
2011-03-03T00:09:42.937Z
@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
CC BY-SA 2.5
2011-03-03T00:34:38.157Z
-1: I don't see how 2SAT is in R^2. I don't see how 2SAT is a "geometric problem."
Robin Kothari
CC BY-SA 2.5
2011-03-03T01:17:42.507Z
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
CC BY-SA 2.5
2011-03-03T01:36:24.313Z
@Robin
I went ahead and clarified in my original comment.
Kaushik Shankar
CC BY-SA 2.5
2011-03-03T03:04:51.633Z
I agree with Robin.  And the same criticism applies to 2- and 3-dimensional matching.  (In addition, I do not know what you mean by the assertions “2-SAT directly maps to 2DM” and “3-SAT directly maps to 3DM.”)
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-03T00:03:31.087Z
2011-03-07T14:02:05.730Z
2011-03-07T14:02:05.730Z
Kaushik Shankar
<p>Set cover by half-spaces.</p>

<p>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.</p>

<p>The polytime algorithm in 2d is described here:
<a href="http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/">http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/</a></p>

CC BY-SA 2.5
2011-03-05T16:23:42.030Z
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
CC BY-SA 2.5
2011-03-07T02:52:13.160Z
...and by harder I meant that the disk problem can be lifted (i.e., reduced) to the halfspaces problem in 3d.
Sariel Har-Peled
CC BY-SA 2.5
2011-03-03T14:31:45.000Z
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
CC BY-SA 2.5
2011-03-03T04:20:12.257Z
2011-03-03T04:20:12.257Z
Sariel Har-Peled
<p>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). </p>

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

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

CC BY-SA 2.5
2011-03-02T22:23:10.530Z
Is [3-dimensional matching](http://www.nada.kth.se/~viggo/wwwcompendium/node143.html) geometric?
Jukka Suomela
CC BY-SA 2.5
2011-03-03T00:06:51.590Z
not really. the "3-dimensional" is in cartesian, not Euclidean sense.
Suresh Venkat
<cc.complexity-theory><reference-request><cg.comp-geom>
Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?
Bob Fraser
# Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?

(Asked by: username_0 on 2011-03-02)

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$?

**Tags:** cc.complexity-theory, reference-request, cg.comp-geom
> **Comments:**
> **username_1**: Is [3-dimensional matching](http://www.nada.kth.se/~viggo/wwwcompendium/node143.html) geometric?  
> **username_2**: not really. the "3-dimensional" is in cartesian, not Euclidean sense.  

---

## 6 answers

### Answer by username_11 on 2011-03-03. Score: 25 | Accepted answer

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/>

> **Comments:**
> **username_0**: 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?  
> **username_11**: 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...  
> **username_11**: ...and by harder I meant that the disk problem can be lifted (i.e., reduced) to the halfspaces problem in 3d.  

---

### Answer by username_3 on 2011-03-02. Score: 29

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).

> **Comments:**
> **username_4**: Are you sure about the planar case?  The algorithms you cite fundamentally require exact real arithmetic!  http://cstheory.stackexchange.com/questions/4034/complexity-of-computing-shortest-paths-in-the-plane-with-polygonal-obstacles  
> **username_3**: 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.  
> **username_0**: 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.  

---

### Answer by username_4 on 2011-03-03. Score: 20

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](http://arxiv.org/abs/math/0012177). *J. Algorithms* 2004.]

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_5 on 2011-03-03. Score: 16

The realizability problem for $d$-dimensional polytopes is a candidate. When $d \le 3$, it's polynomial-time solvable (by [Steinitz' theorem](http://en.wikipedia.org/wiki/Steinitz%27s_theorem)), but when $d \ge 4$, this is NP-hard. For further information, please look at "[Realization spaces of 4-polytopes are universal](http://dx.doi.org/10.1090/S0273-0979-1995-00604-X)" by Richter-Gebert and Ziegler (there is [an arxiv version](http://arxiv.org/abs/math/9510217) as well), and the book "[Lectures on Polytopes](http://www.springer.com/mathematics/geometry/book/978-0-387-94365-7)" (2nd printing) by Ziegler.

> **Comments:**
> **username_3**: More specifically than saying that it's NP-hard, it's complete for $\exists\mathbb{R}$, the existential theory of the real numbers.  
> **username_0**: I hadn't seen this problem before, thanks.  
> **username_6**: Again, like David Eppstein's answer, harder (probably) than NP-complete.  

---

### Answer by username_7 on 2011-11-12. Score: 11

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](http://dl.acm.org/citation.cfm?id=1283439)

> **Comments:**
> **username_2**: That's also a good example.  

---

### Answer by username_8 on 2011-03-03. Score: -2

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](http://en.wikipedia.org/wiki/Matching_%28graph_theory%29), 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](http://en.wikipedia.org/wiki/3-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$.

> **Comments:**
> **username_2**: what does it mean to say that 2SAT is "in" R^2 ?  
> **username_8**: @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$.  
> **username_9**: -1: I don't see how 2SAT is in R^2. I don't see how 2SAT is a "geometric problem."  
> **username_8**: 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.  
> **username_8**: @Robin I went ahead and clarified in my original comment.  
> **username_10**: I agree with Robin.  And the same criticism applies to 2- and 3-dimensional matching.  (In addition, I do not know what you mean by the assertions “2-SAT directly maps to 2DM” and “3-SAT directly maps to 3DM.”)  

---

