Open Problems in Computational geometry

https://topp.openproblem.net/

92•nill0•8mo ago

Comments

wrsh07•8mo ago

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•8mo ago

Last update to mark a problem as solved was in December last year: https://github.com/edemaine/topp/pull/10

rurban•8mo ago

You just need to file a simple PR to mark a problem as solved though. I cannot get much simplier

jll29•8mo ago

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•8mo ago

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•8mo ago

Are there any solutions similar to those found at https://www.cs.ru.nl/~freek/100/ ?

ogogmad•8mo ago

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•8mo ago

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•8mo ago

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•8mo ago

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•8mo ago

Was hoping for some pretty pictures.... since there are none this article isn't for me I guess.

rurban•8mo ago

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

Tiny C Compiler

SectorC: A C Compiler in 512 bytes

Speed up responses with fast mode

Brookhaven Lab's RHIC concludes 25-year run with final collisions

Software factories and the agentic moment

OpenCiv3: Open-source, cross-platform reimagining of Civilization III

Stories from 25 Years of Software Development

Hoot: Scheme on WebAssembly

The F Word

FDA intends to take action against non-FDA-approved GLP-1 drugs

First Proof

Vocal Guide – belt sing without killing yourself

I write games in C (yes, C) (2016)

Al Lowe on model trains, funny deaths and working with Disney

Eigen: Building a Workspace

Start all of your commands with a comma (2009)

Show HN: I saw this cool navigation reveal, so I made a simple HTML+CSS version

Show HN: A luma dependent chroma compression algorithm (image compression)

The silent death of Good Code

Selection rather than prediction

The AI boom is causing shortages everywhere else

Microsoft account bugs locked me out of Notepad – Are thin clients ruining PCs?

Reinforcement Learning from Human Feedback

Unseen Footage of Atari Battlezone Arcade Cabinet Production

A Fresh Look at IBM 3270 Information Display System

Learning from context is harder than we thought

Coding agents have replaced every framework I used

72M Points of Interest

Where did all the starships go?

Show HN: Look Ma, No Linux: Shell, App Installer, Vi, Cc on ESP32-S3 / BreezyBox