[vanderZwan]

Well, conceptually maybe, but I have some doubts regarding:

> 2) Compute Delaunay in 3D

How much slower is 3D triangulation compared to 2D? How does it scale with more points? And just as importantly: how complex does the algorithm get when we want to improve performance?

I'm not saying you're wrong - if anything I hope I'm wrong, but I suspect the answers to my questions are "significant", "badly", and "very", which would mean this is not easier/more robust in practice (or it comes at the price of being unacceptably slow).

The reason I think so is Julia's Voronoi/Delaunay package[0]. It implements an algorithm from an extremely dense (to non-astronomers) astronomy paper[1]. Even the name is intimidating: "E pur si muove: Galiliean-invariant cosmological hydrodynamical simulations on a moving mesh"

Page five and six of the paper lists a short history of triangulation algorithms, making it clear that Delaunay triangulation so important for scientific research that many people have given it considerable thought.

Sadly, I cannot really follow the algorithm explained in that paper. It seems to fall for the inevitable "algorithm by PhDs with complex enough math that you need a comparable PhD to being to grok it"-curse (and/or I am just too dumb).

Of course, if someone already did the hard work of implementing really fast and robust 3D Delaunay libraries to steal from... ;)

(the Julia package only implements the 2D algorithm. Sadly)

[0] https://github.com/JuliaGeometry/VoronoiDelaunay.jl

[1] https://arxiv.org/abs/0901.4107

[contravariant]

Computing Delaunay on a sphere isn't exactly the easiest either, distances get rather tricky and there's no simple projection that preserves all of them.

[amitp]

If I understand correctly, the stereographic projection does handle Delaunay+Voronoi on a sphere, for all points except the south pole. See section 8.5 of http://www.cis.upenn.edu/~cis610/convex8.pdf

[vanderZwan]

True, but it can be decomposed into different steps at least (trying to find less-wrong projections, effective 2D triangulation).

The complexity of working with 3D spaces typically feels worse and harder to untangle to me.

It's like.. I dunno, having two jugglers juggling ten balls each and passing them between each other, or one being asked to juggle twenty[0]. But that is a personal thing - it may also just be sign I'm bad at maths in 3D space.

[0] http://www.juggling.org/papers/limits/

[contravariant]

In the end it's a trade-off between having an extra dimension to deal with, or having to deal with a non-euclidean space. Between the two it's nearly always easier to go for the higher dimensional euclidean one, but exceptions might exist.

Of course if you want an approximate solution then projecting the sphere to 2D might be an option, but glueing together the different projections required could be a bit of a hassle.