(Author here). I don't know enough about computational geometry to say anything intelligent here, but there has been a lot of progress in triangulation since 19

(Author here). I don't know enough about computational geometry to say anything intelligent here, but there has been a lot of progress in triangulation since 1985. The algorithm described here wasn't even state-of-the-art back then in the case that all your points are known up-front -- Guibas & Stolfi describe a separate O(nlog(n)) algorithm that also starts by sorting, and which can be parallelized, unlike the incremental approach. The sweep-hull algorithm doesn't seem parallelizable, but I have not actually read the papers so take that with a grain of salt.