[HN Gopher] Open Problems in Computational geometry
___________________________________________________________________
Open Problems in Computational geometry
Author : nill0
Score : 83 points
Date : 2025-05-17 09:37 UTC (13 hours ago)
(HTM) web link (topp.openproblem.net)
(TXT) w3m dump (topp.openproblem.net)
| wrsh07 wrote:
| 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)
|
| ^ https://erikdemaine.org/curved/MoMA/
| yorwba wrote:
| Last update to mark a problem as solved was in December last
| year: https://github.com/edemaine/topp/pull/10
| rurban wrote:
| You just need to file a simple PR to mark a problem as solved
| though. I cannot get much simplier
| jll29 wrote:
| 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)
| boxfire wrote:
| Definitely out of date, e.g. the 3SUM subquadratic conjecture
| (probably 11) has been solved and improved on [1].
|
| If it's not been already there's immediate application, e.g.
| problem 41.
|
| [1]:https://link.springer.com/article/10.1007/s00453-015-0079-6
| mazsa wrote:
| Are there any solutions similar to those found at
| https://www.cs.ru.nl/~freek/100/ ?
| ogogmad wrote:
| 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 wrote:
| 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.
| bubblyworld wrote:
| A technicality is that those compressors need to _provably_
| predict properties of said geometric objects to be interesting
| to mathematicans (a statement which itself needs appropriate
| encoding in mathematical language - what exactly you want
| probably depends on the problem you hope to solve). Something
| that superficially looks good but works as a black box wouldn
| 't cut it.
|
| My understanding of ML interpretability research at the moment
| is that it's very early days - too early, perhaps, to hope for
| a general purpose compressor algorithm that produces proofs of
| it's own workings (that seems like the holy grail). But of
| course I would love to be wrong!
| jll29 wrote:
| 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.
| lordfrito wrote:
| Was hoping for some pretty pictures.... since there are none this
| article isn't for me I guess.
| rurban wrote:
| Indeed. With more pictures such as at
| https://topp.openproblem.net/p59 I foresee that there will be
| much more solutions. You don't need to be an expert to solve
| most, but they hide themselves behind expert language
___________________________________________________________________
(page generated 2025-05-17 23:01 UTC)