I love this graph. I noticed that the way you list the edges misses those that are on the hull—maybe on purpose? And, for a faster and imo simpler check of whether an edge is Gabriel, you can test > delaunay.find(midpoint[0], midpoint[1], ti) === ti or better, to avoid precision issues where tj would be closer to the midpoint than ti: > [ti, tj].includes(delaunay.find(midpoint[0], midpoint[1], ti)) (This implies that we should keep the ti reference somewhere in the link—I don't think we need to materialize the points in the links, only when we draw.) And now I want to have the spherical Gabriel graph too :)

Hi Fil, thank you for your comment! > I noticed that the way you list the edges misses those that are on the hull That was my mistake, I have fixed it now, thanks for pointing that out! > [ti, tj].includes(delaunay.find(midpoint[0], midpoint[1], ti)) This is a very good suggestion! Just I think it can not be started with ti coz it might skip the actual point somehow. Have updated the code with [ti, tj].includes(delaunay.find(midpoint[0], midpoint[1])) About the spherical Gabriel graph, I am not very good at math and geometry, but I think the above Gabriel graph is defined in the Euclidean plane? Would like to know the rules about Gabriel graph on a spherical surface...

delaunay.find should absolutely be started with ti, so you get O(1) performance instead of O(sqrt(N)) when starting from node 0; is there a case where it wouldn't work? I'll try to make a notebook with spherical Gabriel; we'll just have to replace the euclidian distance by the spherical distance, I guess. It will be a nice complement to the Urquhart graph.

There is a small bug in the test of whether ti and tj are in different sets; the correct test would be (!((ti < setA.length) ^ (tj < setA.length)))

> delaunay.find should absolutely be started with ti you are right, I misunderstood the algorithm of delaunay.find() before. > the correct test would be (!((ti < setA.length) ^ (tj < setA.length))) hmm i dont think so... let's say if ti and tj are all from setB, (ti < setA.length) will be 0, and same for (tj < setA.length), thus ((ti < setA.length) ^ (tj < setA.length)) will be 0 and (!((ti < setA.length) ^ (tj < setA.length))) will be 1. the logical NOT is not needed

All good. For some reason I thought the code was checking (ti - A.length) * (tj - A.length).

Here's the spherical Gabriel graph https://observablehq.com/@visionscarto/world-cities-gabriel

Cool notebook!