Open Problems in Computational geometry
7 comments
·May 17, 2025wrsh07
Does anyone know if this is still up-to-date?
All three authors are large contributors to the field (the book _discrete and computational geometry_ by O'Rourke & Devadoss is excellent), Demaine has some origami in the collection at MoMA NYC^, Mitchell found a ptas for euclidian tsp (Google it - the paper is readable and there is another good write up of his vs Arora's)
jll29
Thanks for the pointer, I just saw the 2nd edition of Discrete and Computational Geometry will be coming out in July: https://www.amazon.com/-/en/Discrete-Computational-Geometry-... (I preordered a copy)
yorwba
Last update to mark a problem as solved was in December last year: https://github.com/edemaine/topp/pull/10
mazsa
Are there any solutions similar to those found at https://www.cs.ru.nl/~freek/100/ ?
ogogmad
Is any of the new machine learning tech promising here? I recall some new invariants of minimal surfaces were discovered only a few years ago by a DeepMind-made AI - and that's before LLMs. I'm wondering if AI can invent notions as powerful as homology groups: It could go about this by constructing lossy compressors whose outputs can still be used to accurately predict properties of geometric objects. That is what homology groups and the like are for.
jebarker
This does seem like one math domain where there's some potential for program synthesis approaches like the recent AlphaEvolve and others. I say that because some of these problems you could feasibly write automatic evaluation code and solve them by the LLM spitting out a constructor for solutions and then doing hill climbing. That's not true in many areas of math though. There's also problems here that require a proof and maybe would be approachable eventually using automated theorem proving. But there's also problems that don't obviously fit into either of those categories.
It's a great idea to collect open problems, to give them a name and unique number, to collect status updates, and to provide related literature references. It would be good to keep this open for submitting new problems also, and I'd like to see similar activities for all sub-areas of mathematics and computer science.
Mathematicians led by Terence Tao are keen to explore new ways for mathematicians to collaborate remotely and online to tackle all open problems together in an open and technology-supported way. I think problem inventories should be part of that, together with proof collections, existing datasets such as the great On-Line Encyclopedia of Integer Sequences (OEIS, at https://oeis.org), and perhaps Jupyter-type notebooks that utilize symbolic algebra systems, theorem provers etc.