¿Pueden cruzarse las líneas que conectan a los vecinos más cercanos?

Question

No tengo ninguna formación en teoría de grafos, así que lo siento si esta es una pregunta básica. Quiero saber si las líneas que conectan a los vecinos más cercanos pueden cruzarse en algunos casos diferentes.

• Me he convencido de que si no hay lazos para el vecino más cercano vecino más cercano es imposible que las líneas se crucen. ¿Es esto correcto?
• Creo que podría seguir siendo imposible incluso si se permiten los empates, en cuyo caso se pueden trazar cualquiera de las dos líneas o ambas, pero no he dado con un razonamiento sólido que lo respalde.
• Este caso es un poco más complicado. Digamos que los puntos pueden conectarse a su segundo vecino más cercano si aún no se ha trazado una línea que parta de ellos y ya están conectados a su vecino más cercano. En esta condición, dos pares de puntos muy alejados entre sí se conectarían en una línea larga. Cada par tendría una línea que lo conectaría con su vecino más cercano y luego una o dos líneas se conectarían entre los pares. La conexión con el tercer vecino más cercano no está permitida. Me parece que también en este caso no se cruzaría ninguna línea.

No tengo ni idea de por dónde empezar a buscar matemáticas formales que respalden estas afirmaciones. ¿Existe una teoría general de las líneas que se cruzan en una red de conexiones de vecinos más cercanos? Se agradecería cualquier ayuda.

Answer 1

Si $A$ tiene un vecino más cercano $B$ , entonces cualquier punto $x$ en el segmento de línea que une $A$ y $B$ está más cerca de $A$ o $B$ pero no a ningún otro punto (ni siquiera empatado):

Supongamos que existe un punto $C$ , de tal manera que $d(x,C) \leq d(x,A),d(x,B)$ para algunos $x$ en $AB$ . Entonces, por la desigualdad del triángulo (la desigualdad es estricta porque sabemos que $C$ no se puede mentir en $AB$ )

\begin{align*} d(A,C) &< d(A,x) + d(x,C) \\ &< d(A,x) + d(x,B) \\ &< d(A,B) \end{align*}

contradiciendo el hecho de que $B$ es el vecino más cercano de $A$ .

Ahora supongamos que hay 4 puntos $A,B,C,D$ , tal que hay una arista entre $A,B$ y entre $C,D$ . Entonces, si las líneas $AB$ y $CD$ se cruzaría, el punto de intersección $x$ estaría estrictamente más cerca de al menos uno de $A$ , $B$ que a cualquier otro punto, y también estrictamente más cerca de al menos uno de $C,D$ que a cualquier otro punto, lo cual es absurdo.

También, por alguna teoría general: Los diagramas de Voronoi y las triangulaciones de Delaunay pueden ser muy útiles a la hora de pensar en estos problemas. Lo anterior equivale en realidad al hecho de que en un diagrama de Voronoi, la línea que conecta dos vecinos más cercanos sólo cruza las celdas de Voronoi de estos dos puntos (que deben ser adyacentes).

EDIT: He pasado por alto algo: Si $A$ es el punto más cercano a $B$ , entonces eso no implica necesariamente que $B$ es también el punto más cercano a $A$ . Supongo que quieres considerar el gráfico formado por la conexión de cada punto con su vecino más cercano (por lo que puede ocurrir que varias líneas sean adyacentes a un determinado punto). Sin embargo, el argumento era fácil de arreglar.

Answer 2

Supongamos que $A,B,C,D$ son puntos distintos, $B$ es el más cercano a $A$ de $B,C,D$ y $D$ es el más cercano a $C$ de $A,B,D$ (con posibles empates). Supongamos que las líneas $AB$ y $CD$ cruzar en $E$ . Si $E$ es $A$ o $B$ está más cerca de $C$ que $D$ es, contradiciendo la suposición de que $D$ es el más cercano a $C$ . Del mismo modo, si $E$ es $C$ o $D$ está más cerca de $A$ que $B$ es. El caso restante es cuando $E$ es distinto de $A,B,C,D$ . Entonces $d(A,D) < d(A,E) + d(E,D)$ y $d(B,C) < d(B,E) + d(E,C)$ así que $d(A,D) + d(B,C) < d(A,E)+d(E,B) + d(C,E)+d(E,D) = d(A,B)+d(C,D)$ . Pero por suposición $d(A,B) \le d(A,D)$ y $d(C,D) \le d(B,C)$ así que $d(A,B) + d(C,D) \le d(A,D)+d(B,C)$ contradicción.