Optimize placement to yield Shortest Distance to 20 Points

Question

Hey guys looking for a maths wiz or IT expert to help me solve this problem.

I have 20 points (say 20 people) in a 2D plane (X,Y) all the coords are given for each of the 20 people.

I would like to place a Creeper so the total distance to the people is minimised.

This solution is fairly easy: you simply get the average of all the 20 x values and 20 y values average and that point would be center point to place the creeper.

The real problem is this:

I am to place 2 Creepers (Creeper A and Creeper B) on to the 2D plane, if a person is close to Creeper A it doesn't need to be "served by Creeper B".

What is the position of the 2 creepers (Xa, Ya), (Xb, Yb) such that the total distance between people and creepers is minimised?

Note it's possible for 1 creeper to serve say 18 people and the other services just 2. They do not need to each serve an equal number of people like 10 each.

Answer 1

Your problem is a version of the facility location problem called Multi-source Weber problem. It’s a NP-hard problem but many exact algorithm exists to solve it on the plane. See for example Slide 40 of http://www.imus.us.es/PDCOR15/doc/Transparencias_Victor_Blanco.pdf

Answer 2

I'm not sure I completely understand your question, but I'll give it a shot! You have 20 coordinates of the form $(x_{i}, y_{i})$ on your axis. Your aim is to place two "creepers" on the plane such that the distance between the coordinates and one particular creeper is minimized. I'll demonstrate a mathematical example that may be useful.

Suppose I have several $(x, y)$ points which I believe can be approximated by the equation $y = ax^2 + b$. If I plug in each $(x_{i}, y_{i})$ coordinate into this equation, it will return coefficients for the $a$ and $b$ variables and simply the y-coordinates on the left side. If we place these coefficients of $a$ and $b$ into an "overdetermined" matrix $A$, we can compute the least squares solution; this returns a value for $a$ and $b$ such that the distance between the given coordinates and the function $y$ is minimized. The values for $a$ and $b$ (a two dimensional vector) are calculated as,

$\gamma = (A^TA)^{-1}A^Tb$

where $b$ is a column holding the $y$-values. If you set $a$ and $b$ of your equation to the values in this vector, you have your line of best fit.

If it so happens that the coordinates in your problem could be approximated by some equation, you could use the least-squares process. Then, find the domain of your coordinate set and, from there, the midpoint between the lowest and highest $x$ value. You could set that midpoint as a kind of division line on the domain for your least-squares solution. The distance, therefore, will be minimized between each point and the function; you could set your program to choose the leftmost "creeper" if a coordinate is on one side of the domain and the other "creeper" if the coordinate is on the other side. The downfall is that the "creeper" will no longer be a point, so to speak, but rather a function; not sure if that would work in your implementation.

Coordinate is "served" by A if is in the domain of A (same for B). Sorry for the crude drawing –– hope this helped a bit or gave you some ideas –– check out this link for great info on least-squares approximation: https://medium.com/@andrew.chamberlain/the-linear-algebra-view-of-least-squares-regression-f67044b7f39b