Hacker News Reader

Great article!

How does this algorithm compare to others, e.g. sweep algorithms like the one used by delaunator[0]?

An obvious difference is sweep algorithms sort the points in some way before adding them, is that a key to efficiency gains?

0: https://github.com/mapbox/delaunator/blob/main/README.md#pap...

View on HN

(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.

Reply on news.ycombinator.com