# Shortest path on dynamic graph

1. Mar 17, 2008

### Dragonfall

Shortest path on dynamic "graph"

Suppose you have n objects orbiting Earth with velocities v1, ..., vn. Starting from t=0, the objects are at positions x1,..., xn; how do you calculate at what point they will be at a state such that the shortest path (arcs of great cirlces) connecting all of them will exist? Is it possible that no such configuration exists (there will always be a shorter one)?

2. Mar 19, 2008

### Dragonfall

Anyone?

3. Mar 22, 2008

### mubashirmansoor

I don't know how to describe the answer mathematically but I think such a state exists since the satellites have different velocities. So considering an infinite time there will be a high probability for such a state to exist.

4. Mar 22, 2008

### Crosson

Since you say the paths joining the particles are arcs of great circles, I assume that x1, x2, ... ,xn are each two-dimensional coordinates $x_i = (\theta_i,\phi_i)$ and all of the objects are constrained to a spherical shell with radius greater than the earth.

First, consider the case where the all the objects lie on a great circle (wolog, take $\phi_i$ t be zero for each i). Two cases:

Case 1: For each $i,j$ we have $\frac{v_i}{v_j}$ be a rational number. In this case there is some time t* (in fact infinitely many such times since the motion is periodic in this case) such that $x_i = x_j$ for all i,j. In other words, all the "objects" collide simultaneously at time t*. The proof of this consist of trig identities.

Case 2. If any two of the orbits are not commensurate, then there is always a shorter distance. This is a consequence of the above trig identities and the fact that the image of the Sequence {Sin(n)} is dense in [0,1].

The extension to the general case only requires that we consider not the ratios between the magnitudes of the velocities, but rather all possible ratios between (both of) the components of (each of) the velocities. If these ratios are all rational, then there is a time when the particles will coincide; otherwise there will always be a shorter time. The proof is in the same spirit as the above.

5. Mar 23, 2008

### Dragonfall

Suppose I want to graph the infimum something like this, what software would I have to use?

6. Mar 23, 2008

### Crosson

The infimum is always zero, I apologize for not making that clear.

It sounds like you might be more interested in a statistical analysis, e.g. what is the chance that the path between the objects is smaller than distance x before time t (where time t could be a billion years).