Nice, spherical geometry is sth. I always wanted to get into. Q: Shouldn't the lines be curved, i.e. the shortest path on a sphere is a minor arc of a great circle so shouldn't the lines in the voronoi be that as well?
They are curved hopefully. Most of them at least - when the line of a cell is longer than a certain amount, I interpolate the lat/lngs across the line and make more segments.