Contrario a esta pregunta.
Digamos que el Tribunal Supremo sólo ha emitido una sentencia que la parte superior e inferior de las carreteras de un paso superior no necesitan estar en el mismo distrito del congreso. Esto hace que los estados con un montón de pasos a desnivel en alto el género de las superficies para el propósito de fraude electoral. Yo, sin escrúpulos matemático, recibe una llamada de mi legislatura del estado, pidiendo que me consulte para ellos acerca de cómo mejor lugar nuevos caminos para lograr el distrito de diseño, a cambio de una generosa cuota.
Específicamente, mi estado es un rectángulo sin carreteras existentes o pasos a desnivel. Ha $n$ distritos del congreso. La legislatura del estado tiene en mente una colección de $\{P_{i,j}\}$ de los polígonos convexos con vacío interior que el azulejo el estado, donde se $i$ rangos de $1$ $n$ $j$ $1$a $m$ por cada $i$, y deseos de cada una de las $P_{i,j},P_{i',j}$ a estar en el mismo distrito del congreso, por lo tanto deben estar conectadas por carreteras (curvas suaves). En cualquier momento que una carretera pasa a través de un polígono de otro distrito del congreso, de un puente debe ser construido a través de ella para evitar la interrupción de los otros distritos. Cualquier momento de los dos caminos se encuentran, de un paso elevado también debe ser construido. Tenga en cuenta que para cualquier fija $i$, algunos, pero no todos los de la $P_{i,j}$ puede estar vacío. La legislatura quiere saber el número mínimo $\mathcal O(n,m)$ de los pasos a desnivel que tiene que ser construido con el fin de facilitar su fraude electoral, en el peor de los casos.
Equivalentemente, tomar un suelo de baldosas de la plaza de la unidad $S$ por polígonos convexos $P_{i,j}$, e $n$-color, de tal modo que en la mayoría de las $m$ de los polígonos que tienen el mismo color. Para cada color $i$, seleccione curvas suaves $\lambda_{i1},\ldots,\lambda_{ir_i}:[0,1]\to S$ tal que $$\bigcup\limits_{j=1}^m P_{i,j}\cup \bigcup\limits_{k=1}^{r_i}\mathrm{im}(\gamma_{ik})$$ is connected. For each color $i$, choose points $p_{i1},\ldots,p_{is_i}$ tal que $$\left(\bigcup\limits_{j=1}^m P_{i,j}\setminus \left(\bigcup\limits_{i'\neq i}\bigcup\limits_{k=1}^{r_{i'}}\mathrm{im}(\gamma_{i'k})\right)\right)\cup \{p_{i1},\ldots,p_{is_i}\}$$ está conectado. Si podemos elegir las curvas y los puntos libremente, a continuación, $\mathcal O(n,m)$ es el peor de los casos (entre todas las opciones de mosaico y colorear) valor mínimo posible de $\sum\limits_{i=1}^n s_i$.
Claramente $\mathcal O(n,1)=0$. Una muy áspera límite superior es $\mathcal O(n,m)\leq n(m-1)(nm-1)$ ya podemos conectar el necesario distritos dibujando $n(m-1)$ curvas, ninguno de los que tocan el límite y cada uno de los cuales se cruza en la mayoría de todos los $\leq nm-1$ otros distritos, y se cruzan cada polígono en líneas rectas. Un áspero límite inferior viene de dividir el cuadrado en $nm$ tiras verticales y colorear de forma cíclica, es decir, rojo, amarillo, azul. rojo, amarillo, azul, etc. Entonces cualquier camino que conecta a todos los distritos del mismo color deben pasar a través de, al menos, todos, pero uno de los distritos de cada una de otro color, por lo $\mathcal O(n,m)\geq (n-1)(m-1)$.
Puede que estos límites puedan ser mejorados, o incluso una fórmula exacta?
Nota: Para aquellos de ustedes que no en los Estados unidos, esta pregunta no tiene mucho sentido a menos que usted está familiarizado con el fraude electoral.
Edit: Esta pregunta fue inspirada por mi legislatura del estado (Kansas), que trató de hacer un congreso en el distrito que consistía en que el conservador tercio occidental del estado, un camino que va por todo el estado, y dos liberal ciudades a lo largo de la frontera oriental.
Edit 2: Para los efectos de este problema, supongo que en la mayoría de los dos caminos que no se encuentran en cualquier paso a desnivel.
