mediana geométrica

En mediana normal , encontramos un punto que tiene suma mínima de distancias. Un concepto similar se aplica en el espacio 2-D. 
Dados N puntos en el espacio 2-D , la tarea es encontrar un solo punto (x, y) desde el cual se minimice la suma de las distancias a los puntos de entrada (también conocido como el centro de la distancia mínima). Ejemplos:
 
 

Entrada: (1, 1), (3, 3) 
Salida: Mediana geométrica = (2, 2) con distancia mínima = 2,82843
Entrada: (0, 0), (0, 0), (0, 12) 
Salida: Geométrica Mediana = (0, 0) con distancia mínima = 12 
 

Enfoque: 
a primera vista, parece que el problema nos pide que encontremos el punto medio del centro geométrico (en otras palabras, el centroide) de los puntos de entrada dados. Dado que es el punto «central» de la entrada, la suma de las distancias desde el centro hasta todos los puntos de entrada dados debe minimizarse automáticamente. Este proceso es análogo a encontrar el centro de gravedad de  partículas de masa discreta. El primer caso de prueba de ejemplo incluso da la respuesta correcta. Pero, ¿qué sucede cuando aplicamos la misma lógica al segundo ejemplo?
Podemos ver claramente que el Centro Geométrico, o el Baricentro de  está en  . Entonces, de acuerdo con la fórmula de la distancia euclidiana, la distancia total para viajar desde el centroide hasta los 3 puntos de entrada es  Pero el punto óptimo debería ser , dándonos una distancia total de  Entonces, ¿dónde nos equivocamos?
Intuitivamente, puede pensar que el centroide de los puntos de entrada nos da la media aritmética de los puntos de entrada. Pero lo que requerimos es la Tendencia Central de los puntos de entrada tal que el costo de alcanzar esa tendencia central (o en otras palabras, la Distancia Euclidiana) se minimice. Esto se llama la mediana geométrica de un conjunto de puntos. Es como conceptualmente, una mediana es drásticamente diferente de la media de entradas dadas.
No hay ningún algoritmo correcto definido para encontrar la mediana geométrica. Lo que hacemos para abordar este tipo de problemas es aproximar una solución y determinar si nuestra solución es efectivamente la Mediana Geométrica o no.
Algoritmo 
Hay dos variables importantes: 
 

• current_point: almacena las coordenadas x e y del punto que podría ser la mediana geométrica.
• distancia_mínima: almacena la suma de las distancias euclidianas desde el punto_actual hasta todos los puntos de entrada.

Después de cada aproximación, si encontramos un nuevo punto desde el cual la suma de las distancias es menor, entonces actualizamos los valores del punto actual y la distancia mínima al nuevo punto y la nueva distancia.
Primero, encontramos el Centroide de los puntos dados, lo tomamos como el punto_actual (o la mediana) y almacenamos la suma de las distancias en la distancia mínima. Luego, iteramos sobre los puntos de entrada dados, suponiendo que cada punto de entrada sea la mediana y luego calculando la distancia a otros puntos. Si esta distancia es menor que la distancia_mínima, entonces actualizamos los valores antiguos de punto_actual y distancia_mínima a los nuevos valores. De lo contrario, los valores antiguos siguen siendo los mismos.
Entonces entramos en un bucle while. Dentro de ese bucle, nos movemos una distancia de test_distance (asumimos una test_distance de 1000 para este ejemplo) desde el punto_actual en todas las  direcciones (izquierda, arriba, derecha, abajo). Por lo tanto obtenemos  nuevos puntos. Luego calculamos la distancia desde estos nuevos puntos hasta los puntos de entrada dados. Si esta suma de distancias es menor que la distancia_mínima anterior, entonces actualizamos los valores antiguos de punto_actual y distancia_mínima a los nuevos valores y repetimos el bucle while. De lo contrario, dividimos test_distance por  y luego repetimos el ciclo while.
La condición de terminación para el bucle while es un cierto valor llamado «límite_inferior». Cuanto menor sea el valor, mayor será la precisión de nuestra aproximación. El bucle termina cuando lower_limit excede test_distance.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// To store a point in 2-D space
struct Point {
    double x, y;
};
 
// Test points. These points are the left,
// up, right and down relative neighbours
// (arranged circularly) to the
// current_point at a distance of
// test_distance from current_point
Point test_point[] = { { -1.0, 0.0 },
                       { 0.0, 1.0 },
                       { 1.0, 0.0 },
                       { 0.0, -1.0 } };
 
// Lowest Limit till which we are going
// to run the main while loop
// Lower the Limit higher the accuracy
double lower_limit = 0.01;
 
// Function to return the sum of Euclidean
// Distances
double distSum(Point p,
                        Point arr[], int n)
{
    double sum = 0;
    for (int i = 0; i < n; i++) {
        double distx = abs(arr[i].x - p.x);
        double disty = abs(arr[i].y - p.y);
        sum += sqrt((distx * distx) + (disty * disty));
    }
 
    // Return the sum of Euclidean Distances
    return sum;
}
 
// Function to calculate the required
// geometric median
void geometricMedian(Point arr[], int n)
{
 
    // Current x coordinate and y coordinate
    Point current_point;
 
    for (int i = 0; i < n; i++) {
        current_point.x += arr[i].x;
        current_point.y += arr[i].y;
    }
 
    // Here current_point becomes the
    // Geographic MidPoint
    // Or Center of Gravity of equal
    // discrete mass distributions
    current_point.x /= n;
    current_point.y /= n;
 
    // minimum_distance becomes sum of
    // all distances from MidPoint to
    // all given points
    double minimum_distance =
       distSum(current_point, arr, n);
 
    int k = 0;
    while (k < n) {
        for (int i = 0; i < n, i != k; i++) {
            Point newpoint;
            newpoint.x = arr[i].x;
            newpoint.y = arr[i].y;
            double newd =
                   distSum(newpoint, arr, n);
            if (newd < minimum_distance) {
                minimum_distance = newd;
                current_point.x = newpoint.x;
                current_point.y = newpoint.y;
            }
        }
        k++;
    }
 
    // Assume test_distance to be 1000
    double test_distance = 1000;
    int flag = 0;
 
    // Test loop for approximation starts here
    while (test_distance > lower_limit) {
 
        flag = 0;
 
        // Loop for iterating over all 4 neighbours
        for (int i = 0; i < 4; i++) {
 
            // Finding Neighbours done
            Point newpoint;
            newpoint.x = current_point.x
                 + (double)test_distance * test_point[i].x;
            newpoint.y = current_point.y
                 + (double)test_distance * test_point[i].y;
 
            // New sum of Euclidean distances
            // from the neighbor to the given
            // data points
            double newd = distSum(newpoint, arr, n);
 
            if (newd < minimum_distance) {
 
                // Approximating and changing
                // current_point
                minimum_distance = newd;
                current_point.x = newpoint.x;
                current_point.y = newpoint.y;
                flag = 1;
                break;
            }
        }
 
        // This means none of the 4 neighbours
        // has the new minimum distance, hence
        // we divide by 2 and reiterate while
        // loop for better approximation
        if (flag == 0)
            test_distance /= 2;
    }
 
    cout << "Geometric Median = ("
         << current_point.x << ", "
         << current_point.y << ")";
    cout << " with minimum distance = "
         << minimum_distance;
}
 
// Driver code
int main()
{
 
    int n = 2;
    Point arr[n];
    arr[0].x = 1;
    arr[0].y = 1;
    arr[1].x = 3;
    arr[1].y = 3;
    geometricMedian(arr, n);
 
    return 0;
}

//JavaScript implementation of the approach
 
// To store a point in 2-D space
class Point {
    constructor(x, y){
        this.x = x;
        this.y = y;
    }
}
 
// Test points. These points are the left,
// up, right and down relative neighbours
// (arranged circularly) to the
// current_point at a distance of
// test_distance from current_point
let test_point = [new Point(-1, 0),
                  new Point(0, 1),
                  new Point( 1, 0),
                  new Point(0, -1)];
 
 
// Lowest Limit till which we are going
// to run the main while loop
// Lower the Limit higher the accuracy
let lower_limit = 0.01;
 
// Function to return the sum of Euclidean
// Distances
function distSum(p, arr, n)
{
    let sum = 0;
    for (let i = 0; i < n; i++) {
        let distx = Math.abs(arr[i].x - p.x);
        let disty = Math.abs(arr[i].y - p.y);
        sum += Math.sqrt((distx * distx) + (disty * disty));
    }
 
    // Return the sum of Euclidean Distances
    return sum;
}
 
// Function to calculate the required
// geometric median
function geometricMedian(arr, n)
{
 
    // Current x coordinate and y coordinate
    let current_point = new Point(0, 0);
     
    for (let i = 0; i < n; i++) {
        current_point.x = current_point.x + arr[i].x;
        current_point.y = current_point.y + arr[i].y;
    }
 
    // Here current_point becomes the
    // Geographic MidPoint
    // Or Center of Gravity of equal
    // discrete mass distributions
    current_point.x /= n;
    current_point.y /= n;
 
    // minimum_distance becomes sum of
    // all distances from MidPoint to
    // all given points
    let minimum_distance = distSum(current_point, arr, n);
 
    let k = 0;
    while (k < n) {
        for (let i = 0; i < n, i != k; i++) {
            let newpoint = new Point(0, 0);
            newpoint.x = arr[i].x;
            newpoint.y = arr[i].y;
            let newd = distSum(newpoint, arr, n);
            if (newd < minimum_distance) {
                minimum_distance = newd;
                current_point.x = newpoint.x;
                current_point.y = newpoint.y;
            }
        }
        k++;
    }
 
    // Assume test_distance to be 1000
    let test_distance = 1000;
    let flag = 0;
 
    // Test loop for approximation starts here
    while (test_distance > lower_limit) {
 
        flag = 0;
 
        // Loop for iterating over all 4 neighbours
        for (let i = 0; i < 4; i++) {
 
            // Finding Neighbours done
            let newpoint = new Point();
            newpoint.x = current_point.x + test_distance * test_point[i].x;
            newpoint.y = current_point.y + test_distance * test_point[i].y;
 
            // New sum of Euclidean distances
            // from the neighbor to the given
            // data points
            let newd = distSum(newpoint, arr, n);
 
            if (newd < minimum_distance) {
 
                // Approximating and changing
                // current_point
                minimum_distance = newd;
                current_point.x = newpoint.x;
                current_point.y = newpoint.y;
                flag = 1;
                break;
            }
        }
 
        // This means none of the 4 neighbours
        // has the new minimum distance, hence
        // we divide by 2 and reiterate while
        // loop for better approximation
        if (flag == 0)
            test_distance /= 2;
    }
 
    console.log("Geometric Median = (", current_point.x, ", ", current_point.y, ") with minimum distance = ", minimum_distance.toFixed(5));
}
 
// Driver code
let n = 2;
let arr = [
    new Point(1, 1),
    new Point(3, 3)
];
 
geometricMedian(arr, n);
 
// The code is contributed by Nidhi goel

Geometric Median = (2, 2) with minimum distance = 2.82843

Referencias: Mediana Geométrica , Centro de distancia mínima