Skip to main content

Timeline for Undecidable problems in geometry

Current License: CC BY-SA 3.0

4 events
when toggle format what by license comment
Sep 21, 2011 at 15:51 comment added Martin Tancer 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.)
Sep 21, 2011 at 14:19 comment added Igor Rivin 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...)
Sep 21, 2011 at 14:06 comment added Martin Tancer 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.
Sep 21, 2011 at 13:13 history answered Igor Rivin CC BY-SA 3.0