Powerful algorithms too complex to implement [closed]

Question

What are some algorithms of legitimate utility that are simply too complex to implement?

Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication algorithm, which is reasonable to implement but has a constant that makes it useless in practice. I'm looking for algorithms that could plausibly have practical value, but are so difficult to code that they have never been implemented, only implemented in extremely artificial settings, or only implemented for remarkably special-purpose applications.

Also welcome are near-impossible-to-implement algorithms that have good asymptotics but would likely have poor real performance.

Answer 1

I don't think there is any algorithm with practical use that has never been coded, but there are plenty that are difficult to code.

An example of an algorithm that is asymptotically optimal, but very difficult to code is Chazelle's O(n) polygon triangulation algorithm. According to Skiena (author of The Algorithm Design Manual), "[the] algorithm is quite hopeless to implement."

In general, triangulation and other computational geometry algorithms (such as 3D convex hull, and Voronoi diagrams) can be quick tricky to implement. A lot of the trickiness comes down to handling floating point inaccuracies.