algorithm - Path that gets within given distance of each point in order

Question

I have an ordered list of points in a 2D plane. I'd like to find the shortest route such that it gets at least within distance X (or closer) from each point, in the given order. How do I find this route?

I realize that the points that will determine the route (the direction changes there) will lie on circles of perimeter X, centered on the input points themselves, but I didn't get any further.

I'm implementing this in Python, but will be happy for any theoretical help.

Example: (oops I can't count so skipped 7)

Answer 1

Perhaps there's an analytical approach, but this problem certainly can be solved with convex programming. Here's a Python implementation with cvxpy that outputs EPS.

import cvxpy as cp
import numpy as np


def objective(points):
    return np.sum(np.linalg.norm(points[1:] - points[:-1]))


def shortest_path(x, centers):
    points = cp.reshape(cp.Variable(centers.size), centers.shape)
    cost = cp.sum(cp.norm(points[1:] - points[:-1], axis=1))
    constraints = []
    for i, center in enumerate(centers):
        constraints.append(cp.SOC(x, points[i] - center))
    prob = cp.Problem(cp.Minimize(cost), constraints)
    prob.solve()
    return points.value


def main():
    x = 0.05
    centers = np.random.random_sample((10, 2))
    points = shortest_path(x, centers)
    print("%!PS-Adobe-3.0 EPSF-3.0")
    print("%%BoundingBox:0 0 504 504")
    print("72 dup translate")
    print("360 dup scale")
    print("0 setlinewidth")
    for center in centers:
        print(*center, x, 0, 360, "arc")
        print("stroke")
    for i, point in enumerate(points):
        print(*point, "lineto" if i else "moveto")
    print("stroke")


if __name__ == "__main__":
    main()