Skip to main content
2 of 3
added 332 characters in body
subshift
  • 1.1k
  • 1
  • 10
  • 15

More examples are given as answers to a similar question about problems NP-hard in $\mathbb R^3$ but not in $\mathbb R^2$:

  • Set-cover by half-spaces.
  • Finding a shortest path between two points among polygonal obstacles.
  • Determining whether a non-convex polygon/polyhedron can be triangulated without Steiner points.
  • Realizability problem for $d$-dimensional polytopes is a candidate ($d \leq 3$ vs $d \geq 4$).
subshift
  • 1.1k
  • 1
  • 10
  • 15