← Back to context

Comment by wood_spirit

3 hours ago

Beautiful :)

The idea that springs to my mind is to do Delaunay and Voronoi using spherical geometry. I think the article uses flat Euclidean geometry but if we tweak the fifth axiom we could do spherical or hyperbolic?

6 comments

wood_spirit

Reply
srean  2 hours ago

Curious about why you think he is using Euclidean.

From the looks of it the separators seem to be segments of great circles. That is what you would get as loci of angular bisectors.

Angular bisectors is what you would get when you use spherical geometry / arc length metric / Haversine metric.

You could still be right though. Euclidean would get you straight line bisectors, but when you project them back to the surface of the sphere, you get great circles again.

This connects with an important point (no pun intended):

People often use Haversine distance to find nearest neighbours on the globe. As long as you want to compute them modulo a hemisphere, this is unnecessary. Haversine distance and Euclidean restricted to the sphere are monotonic transforms of each other. Therefore the nearest point will be the same regardless of which one you used.

orthoxerox  2 hours ago

There's an algorithm that does it. I wrote a hobby implementation ten years ago. Basically, it's a modification of the sweeping line algorithm that sweeps the sphere from pole to pole.

edit: Found the code. Looks like I instead ended up simply building a convex hull (which is the Delaunay triangulation) and deriving the Voronoi diagram from it.