A while ago I needed an algorithm for Delaunay Triangulation (see, for example, this article). I expected to be able to find lots of standard, current implementations – I didn’t. After a lot of searching, I found David Sinclair’s algorithm, S-Hull. Although it sounded efficient, I couldn’t use his code as it stood so I rewrote it; the results (C++ and C#) are now available on David’s website. It’s a very difficult algorithm to get right (in fact, to be exactly right in general requires infinite-precision arithmetic); I found this paper and the program it refers to (DTT) invaluable.