I'm trying to find the "looped" route with the lowest value of D/n
, where D=Distance
, and n=Number_of_points
, for a cloud of 3D points. However there are a few conditions.
Conditions:
Each point must have one or more points in the route that are greater than $X$ distance away.
Not every point needs to be passed through.
I will try and explain what I mean: Imagine a system of delivery routes, whereby you get paid only if the delivery point is greater than $X$ meters away from the pickup point.
So, if you travel point $A \rightarrow B$ where the distance is $X$, you get paid, but you have been paid once in $X$. If you have say 10 equidistant points on a circle with circumference $X$. The distance in a line between them is $X/10$. So you are stopping once every $x/10$ to pick up a new package. Now, once you travel half way around the circle to point 5, you can deliver the package from the starting point and get paid. This means once the route has been completed halfway, you are getting paid every $X/10$ instead. Much more efficient.
Now here is the kicker, my data is not in a neat circle, but rather a cloud of 3D points.
Which algorithm or set of algorithms could be used to determine the most efficient route between the number of points?
Sorry if I horribly explained my problem, from what I understand the problem might be NP-complete but if an approximate solution can be calculated, that would work.