So I always thought that the optimal solution for triangulation was $O(nlog(n))$. However I found this that claims that 30 years ago someone came up with a very complex linear algorithm.
I have not been able to find the paper. I found this which seems to be by the same author but the year of publication is almost 20 years off according to the slides.
The first question is, does anyone know the original paper?
The second question is if someone knows of an open source implementation of this algorithm, ideally with accompanying documentation/explanation notes.