what-if.xkcd.com: regiones punzantes (simplemente conectadas) en la esfera 2 con pocas geodésicas

Question

En la última ¿qué-si Randall Munroe pedir el número más pequeño de geodesics que se cruzan todas las regiones de un mapa. La siguiente muestra que las cinco vías de satélites suficiente para cubrir los 50 estados de los Estados Unidos:

Una configuración similar, donde las líneas son en realidad grandes círculos es pretendido por el autor:

Todos están ligeramente curvadas, ya que la Tierra gira debajo de los satélites, pero resulta que esta disposición de líneas también funciona para la versión mucho más simple de la pregunta que ignora el movimiento orbital: "¿cuántas rectas (gran círculo), las líneas se tarda para que se cruzan cada estado?" Para ambas versiones de la pregunta, mi mejor respuesta es una versión de la disposición anterior.

Ha habido un poco de trabajo en parecidos problemas. Por apuñalar a (o la búsqueda de las transversales) de segmentos de línea que se vea como un ejemplo Punzante segmentos de línea por H. Edelsbrunner, H. R. Maurer, F. P. Preparata, A. L. Rosenberg, E. Welzl y D. Wood (y los documentos que hacen referencia a él.) o L. M. Schlipf de la tesis con ejemplos de diferentes tipos.

Hay una aproximación algorítmica conocido para hacer frente a este problema (o para el problema más sencillo cuando todas las regiones del mapa son convexas)?

En el caso de los 50 estados de los Estados Unidos, por supuesto, es fácil ver que un gran círculo no es suficiente: tomar dos estados (por ejemplo, Nueva York y Louisiana) de tal manera que todos los grandes círculos que se intersecan aquellos que no pasan a través de un tercer estado (por ejemplo, Alaska). Del mismo modo se puede demostrar que necesitamos al menos 3 grandes círculos.

Tal vez sería útil considerar todos los triples de regiones que no se encuentran en un gran círculo y el uso de este hypergraph información para deducir los límites inferiores.

¿Cuáles son buenos métodos para encontrar reduce los límites?

Randall Munroe las conjeturas de que el 5 es óptimo:

No sé para asegurarse de que el 5 es el mínimo absoluto; es posible hay una manera de hacerlo con cuatro, pero mi conjetura es que no la hay. [...] Si alguien encuentra una forma (o la prueba de que es imposible) me encantaría verlo!

Answer 1

Creo que el camino más fácil para un límite inferior para recoger cuatro estados como Hawai, Alaska, Rhode Island, y la Florida, y mostrar que cualquier geodesics de corte ellos dejan muchos estados descubierto, o de cinco o más en número. Debería ser posible enumerar la máxima de corte geodesics para cada par de estados, y, a continuación, argumentar el uso de tales números. Incluso probando todas las combinaciones de cuatro de corte geodesics participación de más de seis estados debe ser manejable, dicen en la orden de 10^15 combinaciones más o menos.

Answer 2

Aquí está una sugerencia siguiendo con la idea de que el cartel original para mostrar para el caso dado que cuatro es demasiado baja de un salto. Suponga que cuatro geodesics suficiente y buscan una contradicción de la siguiente manera:

Considere la posibilidad de cinco estados que comparten o casi que comparten la misma longitud, por ejemplo, los cinco estados del norte de Texas o los del norte de y como Louisiana. Una geodésica tiene que ejecutar a través de al menos dos de ellos. Debe ser fácil de demostrar con la mano que no las cuatro geodesics ambos pueden cubrir los 48 estados más bajos y tienen una geodésica cubrir tres de estos cinco estados, para cualquier geodésica que cubre al menos tres de estos estados tiene que dejar a muchos otros estados descubierto, incluyendo un grupo de cuatro estados contiguos y un poco más de los grupos de estados (descrito antes). Ahora uno tiene tres geodesics para cubrir este grupo de cuatro y un par de grupos más, y uno de los geodesics tiene que dar al menos dos de este grupo de cuatro. Pero después de intentar cubrir las tres de este grupo de cuatro, uno tiene demasiados miembros de la izquierda más con estos elección de geodesics. El resto de los pocos grupos que deberán contener los estados que no pueden ser cubiertos por dos geodesics solo.

Así que el plan es comenzar con el grupo de los cinco estados, considerar a cada subconjunto de dos o más que pueden ser cubiertos por una geodésica y, a continuación, elegir los grupos (idealmente columnas o arreglos lineales) de los estados en cualquiera de los lados de la línea geodésica que son cuatro o más en número, y considerar las posibilidades restantes cuando se utiliza uno de los tres geodesics para cubrir dos o más de los cuatro estados. Cuando todas estas posibilidades, se pueden encontrar cinco o más estados de la izquierda sobre el cual forma un grafo completo en cinco puntos de la hypergraph de geodésica relaciones. De hecho, para la mayoría de los subconjuntos de los cinco primeros estados del norte de Texas, muchos de los geodesics no golpear, Michigan, Ohio, West Virginia o Virginia. De aquellos que sí golpeó a uno de los cuatro estados, que no llegará a Kentucky, Tennessee, Georgia, o de la Florida.

Mediante un cuidadoso análisis de los estados descubierto desde la consideración de los cinco primeros estados, debería ser posible elegir sabiamente dos o tres candidatos conjuntos de cuatro estados. Para cada uno de estos candidatos, uno debe ser capaz de llegar con cinco o más estados que no son cubiertos por dos geodesics.

Gerhard "Otro Uso Económico De Los Pentagramas" Paseman, 2014.10.01