¿Por qué es cierto que si los rectángulos p se cruzan entre sí debe haber una región (tal vez tan pequeña como un punto) donde todos se superponen?

Answer 1

El teorema de Helly establece que para N objetos convexos en el espacio D-dimensional, el hecho de que cualquiera de ellos (D + 1) se crucen implica que todos juntos tienen un punto común.

Por lo tanto, si cada uno de sus rectángulos tiene un punto común, entonces la respuesta sería “sí”.

Si solo puede asegurarse de que cada dos rectángulos tengan un punto común, no es suficiente. Puedo pensar en un triángulo hecho de tres rectángulos “delgados”, como tres lápices que se tocan en los extremos con cierta superposición. Cada uno de ellos se cruza, pero los tres no tienen un punto en común.

---

Y si está preguntando sobre rectángulos con eje paralelo al eje de coordenadas cartesianas, entonces la respuesta es “sí”.

El área entre {“extremo derecho de los lados izquierdos”, “extremo izquierdo de los lados derechos”, “más bajo de los lados superiores”, “más alto de los lados inferiores”} existe y es su intersección (puede ser una línea o un punto) , o no existe, lo que demuestra que es posible encontrar al menos dos rectángulos de entrada que no se cruzan (separados por una línea horizontal o vertical que se puede encontrar fácilmente).

Answer 2

Como señaló Dima Korolev, esto no es cierto para ningún rectángulo general. Los lados de los rectángulos deben ser paralelos a los ejes. También debe considerar rectángulos cerrados (cerrados en el sentido de topología).

Ahora para resolver este problema modificado, debe observar que se puede pensar que cada rectángulo es un par de intervalos cerrados en la línea Real. Uno de ellos representará su proyección en el eje xy otro representará su proyección en el eje y. Vamos a llamarlos intervalo x e intervalo y.

Para que dos rectángulos se crucen, sus dos intervalos deben cruzarse. Entonces, decir que los rectángulos p se intersecan en pares es decir que sus intervalos xy los intervalos y deben intersectarse en pares.

No, puede mostrar por inducción que si p intervalos cerrados se cruzan por pares, tienen una intersección no vacía. Haga esto tanto para el intervalo x como para el intervalo y y ya está.

Probar esto. Dibujar una línea y visualizar intervalos en ella puede ayudarte.