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