Distancia de Manhattan y desigualdad del triángulo - algoritmo, geometría, distancia

La pregunta surgió en CSAcademy Programming Contest Round 51 aunque. La declaración del problema dice:
"Dadas las distancias a, byc de Manhattan, producen 3 puntos en el espacio 2D, de modo que las distancias de manhattan entre ellas satisfacen los valores mencionados".

Mi acercamiento
Las distancias dadas deben satisfacer: -

(a+b+c)%2==0

La razón es: Ordena las distancias primero de modo que

a<=b<=c

Luego tenemos lo siguiente

|x2-x1|+|y2-y1|=a
|x3-x2|+|y3-y2|=b
|x3-x1|+|y3-y2|=c

Ahora, si 3 puntos tienen coordenadas x1, x2, x3, y1, y2, y3 tales que:

x1<=x2<=x3
y1<=y2<=y3

Entonces podemos abrir el módulo de forma segura para obtener: -

2*(x3-x1)+2*(y3-y1)=a+b+c

A partir de entonces, arreglé (0,0) y (a, 0) y obtuve el tercer punto como:

x3=(a+b-c)/2
y3=(b+c-a)/2

Sin embargo, no pude resolver en el concurso porque no me hice cargo del hecho de que después de la clasificación

a+b>=c should hold (Triangle inequality over Manhattan Distance)

El código para el mismo. aquí.
Así, mis preguntas son las siguientes:

1. ¿Cómo la distancia de Manhattan satisface la desigualdad de triángulos?
2. ¿Alguna métrica de distancia general mantiene la desigualdad del triángulo? (Como Manhattan, Levehnstein (distancia de edición), distancia de Hamming).
3. ¿Es la desigualdad del triángulo una condición necesaria para todas las medidas de distancia? (Eso es lo que debe sostener fundamentalmente).

Respuestas

1 para la respuesta № 1

Creo que el significado es simplemente que los puntos que ha producido no satisfacen los requisitos básicos.

No creo que haya ningún requisito explícito para que los puntos satisfagan la desigualdad del triángulo, esto es solo una propiedad emergente.

Supongamos que a = 0, b = 2, c = 4.

Tu método producirá puntos:

x1,y1 = 0,0
x2,y2 = 0,0
x3,y3 = -1,3

Ahora la distancia 1 a 2 es 0, la distancia 2 a 3 es 4, pero la distancia 1 a 3 también es 4.

La razón para mencionar la desigualdad del triángulo es que, en este caso, puede probar de inmediato que no puede haber soluciones debido a esta desigualdad.

La desigualdad del triángulo se mantendrá para la distancia.métricas donde la distancia se define como una ruta más corta restringida. Esto se debe a que es equivalente a decir que "ir de a a b a c" siempre es al menos tan largo como "ir directamente de a a c".

---