voronoi_diagrams_with_gravity_in_vorosketch

We can use Vorosketch to draw a Voronoi diagram for the following distance measure: the distance between a site *s* and a point *q* is the amount of energy needed to launch a spaceship from *s* into an orbit that reaches *q*, subject to gravitation towards the origin of the coordinate system.

In this thought experiment, we assume that the spaceship has a fixed, constant weight and that *q* is stationary. The speed of a small object at position *X* in an elliptic orbit around a large object in the origin *O* is proportional to √(1/||*OX*|| − 1/(2*a*)), where *a* is the length of the semi-major axis of the ellipse, and therefore the kinetic energy is proportional to 1/||*OX*|| − 1/(2*a*). If we want to launch a space ship from *X* such that it will reach *Y*, we have to give it a direction and a kinetic energy that puts it into an orbit that reaches *Y*. Since this energy increases with *a*, we are looking for the orbit that includes *X* and *Y*, has *O* as one of its focal points, and has the smallest possible semi-major axis (non-elliptical, that is, open-ended orbits do not need to be considered: they would require more energy in any case). Note that, in an ellipse, *a* is exactly 1/4 of the length of the path *OXFYO*, where *F* is the second focal point. Therefore, to minimise *a*, we minimise the length of *OXFYO*, which we achieve by putting *F* on the line segment *XY*. Thus, the required energy is proportional to 1/||*OX*|| − 2/(||*OX*||+||*XY*||+||*YO*||). Thus (see fundamentals of Vorosketch), we can get a Voronoi diagram for ten random sites under the distance measure defined above, with a cross marking the origin, black bisectors, coloured sites and regions, contour lines at 0.05 intervals, 1200 × 1200 pixels, and zoomed out to cover the square [−2.5, 2.5] × [−2.5, 2.5], with:

vorosketch -m "1/sr - 2/(sr+L2+fr)" -+ -bci 0.025 -r 1200 -w 2.5 -@ 10

Note that for each site, the first term (1/||*OX*||, that is, **1/sr**) is fixed, and a contour line (locus of points at equal distance to this site) consists of points *Y* with constant ||*XY*||+||*YO*||: that is an ellipse with focal points *X* and *O*, as we can see in the Voronoi diagram above.

Now suppose we define the distance measure the other way around: the distance between a site *s* and a point *q* is the amount of energy needed to launch a spaceship from *p* into an orbit that reaches *s*. Now our distance measure would be encoded by **1/fr - 2/(fr+L2+sr)**, but it turns out that, to get reasonably spaced contour lines, we better take the logarithm and use the -o option to suppress shading of regions with negative values:

vorosketch -m "ln(1/fr - 2/(fr+L2+sr))" -+ -bcoi 0.5 -r 1200 -w 2.5 -@ 10

As the diagram confirms, sending a spaceship from a point *q* to a site *s* that is right between *q* and Earth is easy: we just let the spaceship drop at zero cost. The distance contour lines look more complicated now. However, as Lukas Plätz pointed out to me, the bisectors are relatively simple: a point *X* is equidistant to two sites *Y*_{1} and *Y*_{2} if and only if 1/||*OX*|| − 2/(||*OX*||+||*XY*_{1}||+||*Y*_{1}*O*||) = 1/||*OX*|| − 2/(||*OX*||+||*XY*_{2}||+||*Y*_{2}*O*||), which is equivalent to ||*XY*_{1}||+||*Y*_{1}*O*|| = ||*XY*_{2}||+||*Y*_{2}*O*||. Thus, the bisector under our orbit-to-site distance is the same as the bisector under the Euclidean distance if each site *Y* has an additive weight *YO*; it is well-known that these bisectors are hyperbolic curves.

Do these orbiting distance measures satisfy the triangle inequality?

voronoi_diagrams_with_gravity_in_vorosketch.txt · Last modified: 2023/03/31 07:51 by administrator