Connect all points of a 3D graph with the shortest path

121 Views Asked by At

I have a collection of $(x, y, z)$ points that are all contained in a $1 \times 1 \times 1$ cube with $(x, y, z) \in [0, 1]^3$. I need to find the shortest path to cross all the points. This looks like an minimum spanning path problem in 3D but there are a few tricks that change the problem a little bit:

  1. The planes $(z = 0)$ and $(z = 1)$ are connected, i.e. the points $(2, 3, 0.01)$ and $(2, 3, 0.97)$ are very close and only $0.04$ apart.
  2. I can only move parallel to the Ox, Oy and Oz axes.
  3. It is not so much the distance that matters as the number of displacements (one displacement means one move on one axis, i.e. I may need 1, 2, or 3 moves for going from one point to another).

Does anyone know of an existing or adaptable algorithm that could address this problem?