5 ms·

I thought that a voronoi partition is not possible with only straight lines on a non-euclidean space like that; this leaves me confused.

• wlievens 11y ago
  They must be geodesics, not straight lines
• rspeer 11y ago
  The edges are segments of great circles, which are the reasonable equivalent to a straight line on the surface of a sphere.
  • teraflop 11y ago
    Or another way to look at it: if you model the earth as a perfect sphere, there's a one-to-one monotonic relationship between geodesic distance and distance in a straight line through the earth. Points that are equidistant by one metric are also equidistant by the other. So you could get exactly the same diagram by finding the 3D Voronoi diagram of the airports as a collection of points in space, and then taking the intersection of that with the geoid.
• Bedon292 11y ago
  It looks like you still just use delaunay triangulation on the points on the surface of the sphere. And then he is connecting the resulting vertices with lines along the surface of the sphere. The lines look straight from head on, but are curved in 3d space.
  • VikingCoder 11y ago
    Actually I think you use delaunay tetrahedrization on the points in 3-space. The points HAPPEN to be on the surface of the sphere. Then you intersect the sphere with the polytopes, which result in great arcs.
• deleted 11y ago
  [deleted]
• VikingCoder 11y ago
  I believe Voronoi can be applied on high-dimension points, producing polytopes. So, run Voronoi on 3D points that happen to all be on the sphere... Then intersect the polytopes with a sphere. Tada - great arcs.
• nilkn 11y ago
  You are in fact correct that the boundaries of the Voronoi cells on a non-Euclidean manifold need not be geodesics. Consider for instance the manifold which is a cone with a circular base, and let the sample points be the apex of the cone and the center of the base. The boundary of the two cells thus produced will be a circle parallel to the base, which is not a geodesic on the cone.