Algorithm to spread / declutter points in 1 dimension (on a line)

Question

Is there a non-iterative algorithm to spread out / declutter points on a line?

Example:

Upper line: Initial situation. Lower line: Points have been spread out.

Constraints:

• I would prefer to have a solution that is not based on nudging the points until they stabilize. In other words, I would prefer an algorithm which, for example, solves a set of equations and thus compute the new position for all points "in one go".
• It's a 1-dimensional situation.
• The resulting points should be as close to their initial positions as possible, but maintain some minimal fixed distance to it's neighbors. Approximations are fine though.

Answer 1

Small general-purpose mathematical-optimization based demo:

• LP/QP might differ as penalties are weighted differently!
• cvxpy does give us the necessary linearizations / reformulations for free (e.g. abs)

import cvxpy as cp
import numpy as np
import matplotlib.pyplot as plt

points = np.array([3, 4, 10, 13, 14, 15]) 
min_distance = 2

def solve(quadratic):
  # vars
  x = cp.Variable(points.shape[0])

  # constraints
  constrs = [x[i] - x[i-1] >= min_distance for i in range(1, points.shape[0])]

  # objective
  if not quadratic:
    obj = cp.Minimize(sum(cp.abs(x - points)))
  else:
    obj = cp.Minimize(cp.sum_squares(x - points))

  # setup problem + solve
  problem = cp.Problem(obj, constrs)
  problem.solve()

  return x.value

linear_sol = solve(False)
quad_sol = solve(True)

# visualize
f, (ax0, ax1, ax2) = plt.subplots(3, sharex=True)

colors = [plt.cm.tab10(i) for i in range(points.shape[0])]

ax0.set_title('Input data')
ax1.set_title('linear / abs | LP')
ax2.set_title('quadratic / sum-squares | QP')

for ind, _ in enumerate(points):
  ax0.axvline(points[ind], color=colors[ind])
  ax1.axvline(linear_sol[ind], color=colors[ind])
  ax2.axvline(quad_sol[ind], color=colors[ind])

f.suptitle("Min distance = {}".format(min_distance))
plt.show()

which behaves like: