8
$\begingroup$

Are there any (many) algorithmically undecidable problems in computational (combinatorial/discrete) geometry?

Update: the Wang tiles answer the question with "any". (I have somewhat overlooked to count them when I was browsing the answers to general undecidable problems.) But I still suspect that there are not many examples naturally arising in combinatorial/discrete geometry. And I am of course interested in any such example. I do not count artificial reformulations of problems stated (by the authors) in different settings.

For instance, it was open for quite some time whether STRING graphs (intersection graphs of curves in the plane) are recognizable. However, it turned out that they indeed are. If the answer was opposite, it would be an example of problem I seek for.

(Let me also exclude problems very similar to Wang tiles if there are any.)

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
6
$\begingroup$

The problem to determine whether two 4-manifolds, given as simplicial complexes, are homeomorphic. This was shown to be undecidable by Markov. (Some theories of physics involve a sum over such manifolds, one additive term for each homeomorphism class, and this lead to speculation that physics was noncomputable in some sense [Geroch and Hartle 1986]. I am not sure what the current status of that is.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ John Stillwell in his book "Classical Topology and Combinatorial Group Theory" 1980, gives an excellent background to this archetypal undecidable geometry problem. He shows the full proof for the case of 5-manifolds, which turns out quite a bit simpler than 4-manifolds, but (apparently) has much of the flavour of the Markov proof. I say apparently because I only understand the one for 5-manifolds $\endgroup$
    – Selene Routley
    Commented Sep 23, 2011 at 10:31
5
$\begingroup$

I'm vaguely aware of two examples, but I can't provide any references.

The first is the colored tiling problem. Suppose you're given a finite collection of squares of equal size such that each edge of each square is colored. The collection is said to tile the plane if you can arrange (possibly infinitely many) copies of the squares in the collection in a grid pattern on the plane such that whenever two squares are adjacent along an edge the edge colors match up. It turns out that the problem of determining when a given collection of colored squares tiles the plane contains the halting problem and hence is undecidable.

The second is the problem of determining when two triangulated manifolds are homotopy equivalent. An algorithm for making this determination would necessarily give a solution to the word problem for groups, so it's undecidable.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, the second one I am aware of and I rather count it as a topological problem. $\endgroup$
    – Martin Tancer
    Commented Sep 21, 2011 at 13:55
  • 4
    $\begingroup$ @Paul: Your first example is known as Wang Tiles: en.wikipedia.org/wiki/Wang_tile . $\endgroup$
    – Joseph O'Rourke
    Commented Sep 21, 2011 at 14:36
  • 1
    $\begingroup$ Paul's second example was mentioned by Scott Carnahan in reply to the MO question "What are the most attractive Turing-undecidable problems in mathematics?": mathoverflow.net/questions/11540 . $\endgroup$
    – Joseph O'Rourke
    Commented Sep 21, 2011 at 15:28
2
$\begingroup$

Yes, there are. If you want to get a more informative answer, you might want to ask a more informative question (like, what circle of problems you actually mean...)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Well, in this case I have rather asked more general question in hope to get various examples. Yes there are many branches of computational (combinatorial/discrete) geometry, but I am afraid that I am really not able to write down the complete list of all interesting branches: E.g., questions on points-lines-planes-...-hyperplanes-arrangements, Voronoi diagrams and their modifications, minimum enclosing balls, geometric Ramsey type problems, convex sets, convex huls, partitions, etc. $\endgroup$
    – Martin Tancer
    Commented Sep 21, 2011 at 14:06
  • 3
    $\begingroup$ The problem is that essentially every problem (and thus every undecidable problem) can be phrased as a geometry problem, so you are basically asking for a list of undecidable problem (which is probably not recursively enumerable...) $\endgroup$
    – Igor Rivin
    Commented Sep 21, 2011 at 14:19
  • 2
    $\begingroup$ Yes, with some effort they can be phrased in such a way. However, I still hope that there is a general feeling what is a problem from computational geometry (preferably cobminatorial/discrete). I am, of course, not interested in problems, that can be artificially rephrased into geometric ones, but rather in those that people really phrase as geometric ones. Thus, I am sorry, but I do not agree that the question is wrong because of this issue. (I agree that I originally did some mistake about tagging the question, but I tried to fix this.) $\endgroup$
    – Martin Tancer
    Commented Sep 21, 2011 at 15:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .