Punto de encuentro común de 3 puntos para llegar al 4º punto

Question

Planteamiento del problema: Somos 3 amigos en 3 lugares diferentes $A, B, C$ y quiere llegar a un lugar $D$ . Cada persona tomará un taxi por separado hasta un punto de encuentro común $E$ y luego tomar un solo taxi desde $E$ a $D$ .

¿Cómo puedo encontrar el punto $E$ que minimiza la distancia total recorrida por las cuatro cabinas?

Answer 1

Si $E$ es el punto de encuentro común, está tratando de resolver

$$\min_E \|A-E\| + \|B-E\| + \|C-E\| + \|D-E\|$$

La solución a este problema de optimización es la _mediana geométrica_ $E$ de los tres amigos y el punto de destino $D$ . En general, el cálculo de la mediana geométrica no es sencillo, pero en el caso especial de cuatro puntos existe un algoritmo fácil:

1) Si uno de los cuatro puntos se encuentra en el triángulo formado por los otros, toma $E$ para ser ese punto. En este caso todos los amigos viajan directamente a $D$ (si este es el punto interior) o dos amigos viajan primero al tercero y luego todos los amigos viajan juntos a $D$ .

2) En caso contrario, los cuatro puntos forman un cuadrilátero. Dibuja las diagonales y toma $E$ para ser el punto de intersección.

No es tan obvio que este algoritmo identifique correctamente la mediana; se dan pruebas aquí .