[rosshemsley]

Perhaps an easier (and more robust) way to do this is as follows:

1) Take your points in 3D, and add the point at the origin

2) Compute Delaunay in 3D

3) The 2D faces not containing the origin is your triangulation.

To get the Voronoi tessellation:

1) Circulate the faces of each vertex in order (use orientation test if they are not ordered yet)

2) Connect the circumcenters of each 2D face you visit.

Voilà!

[stevenanthony]

The Delaunay triangulation of a set of points on the sphere is given by the convex hull. The Voronoi vertices on the sphere are given by the facet normals and vice versa. The convex hull is quite fast to compute.

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

[contravariant]

Not sure why you need the point at the origin. In fact I think it fails when you e.g. only have points on one half of the sphere.