# Place points at maximum distance in a convex 2D set

I need to place a given finite set of points within maximum distance of each other on 2D, constrained by a convex boundary, on Python.

Honestly, I'm kind of lost. I have the explicit function to be minimized, but I'm not sure which algorithm I should use to adjust the points recursively. I thought of experimenting with clustering but I'm not sure if this would work.

And, more importantly, I have no idea how to bound the space.

Unfortunately, the convex boundary isn't a rectangle as well; it looks like this:

• This sounds like a problem in the constrained optimization class. The constraints come from the domain shape, one just needs to produce the objective function, like $\sqrt(\sum(r_i-r_j)^2/N)$, or something like that, and put it in the standard optimization solver in Python. This problem is difficult to solve for a large number of points, but perhaps some simplified formulation could be found, using the physics intuition etc. What is the purpose of this distribution of points? May 24 at 23:08
• Thanks for the input! I'm going to use it to simulate phoneme distributions. Jun 8 at 19:00
• While it is clear what maximizing the distance between two points inside a (convex, bounded) region should mean, a careful definition is needed for extending this problem to more points. @Cesareo has articulated a max-min objective function, which seems natural and fairly robust. But other choices are possible.
– hardmath
Jul 6 at 22:20

Giving a region $$\Omega(p)$$ and a set of $$n$$ points $$p_i,\ i = 1,\cdots, n$$ the problem can be stated as a maximization one.

$$\max\left(\min_{i\ne j} \|p_i-p_j\|\right),\ \ \text{such that}\ \ \forall k,\ p_k\in \Omega(p)$$

One way to tackle this problem is by using Evolutive Strategies (CMA-ES). Follows a setup in python

n = 7
penality = 10000000000000

ae = 2
be = 1.1442

def feasible(x, y):
xa = x / ae
yb = y / be
dif1 = xa * xa + yb * yb - 1
dif2 = -(x + 1)

if  dif1 < 0 and dif2 < 0:
return 0
else:
return max(dif1,dif2)

def objective(p):
dist_min = 100000
for i in range(n):
xi = p[2*i]
yi = p[2*i+1]
fi = feasible(xi, yi)

if fi > 0:
return penality
for j in range(i):
xj = p[2*j]
yj = p[2*j+1]

fj = feasible(xj, yj)
if fj > 0:
return penality
dx = xi - xj
dy = yi - yj
dist = np.sqrt(dx*dx + dy*dy)

if dist < dist_min:
dist_min = dist

return -dist_min

import numpy as np
import matplotlib.pyplot as plt
from cmaes import CMA

best_value = 100000000
best = []

if __name__ == "__main__":
optimizer = CMA(mean = np.zeros(2*n), sigma = 0.45)

for generation in range(4000):
solutions = []
for _ in range(optimizer.population_size):
value = objective(x)
if value < best_value:
best.append([generation,-value])
best_value = value
x_best = x
solutions.append((x, value))
optimizer.tell(solutions)

print(best)
print(x)

X = []
Y = []
for i in range(n):
X.append(x_best[2*i])
Y.append(x_best[2*i+1])

print(X)
print(Y)

angle = np.linspace( 0 , 2 * np.pi , 150 )

xc = ae * np.cos( angle )
yc = be * np.sin( angle )
xs = [-1, -1]
ys = [-1,  1]

(figure, axes) = plt.subplots( 1 )

axes.plot( xc, yc, color = 'b' )
axes.plot( xs, ys, color = 'b' )
axes.scatter(X,Y,marker = 'o', color = 'k' )
axes.set_aspect( 1 )
plt.show()