ACTUALIZACIÓN: he creado una web, sencilla aplicación, que permite al usuario mover alrededor de chiqueros, a continuación, calcula automáticamente un conjunto máximo de interiores disjuntos cuadrados entre los puntos (el algoritmo es exponencial, por lo que funciona sólo hasta alrededor de $n=11$ puntos).
Hay $n$ chiqueros, en un infinito desierto. Asumir cada uno de los puntos es un punto en $\Bbb R^2$, y los valores x e y de los puntos son todos diferentes.
Definir un paraíso como un eje alineado a la plaza que toca, al menos, dos de abastecimiento.
Definir $p(n)$ como el número máximo de interiores disjuntos paraísos en el peor de los posibles acuerdos de $n$ chiqueros. ¿Qué es $p(n)$?
ALGUNOS CASOS SIMPLES:
Si el abastecimiento están en la diagonal (por ejemplo,$\{(i,i)|1\leq i\leq n\}$), entonces sólo puede haber un único paraíso entre cada par adyacente de abastecimiento, para un total de $n-1$. Por lo tanto: $p(n) \leq n-1$:
Para $n \leq 5$, se puede comprobar que el $p(n) = n-1$:
- Para $n=1, 2$ esto es obvio.
- Para $n=3$, poner 2 paraísos de la siguiente manera. El fin de los chiqueros en un orden creciente de su valor de x ($x_1 < x_2 < x_3$). Cortar el plano a dos medio-planos mediante una línea vertical a través de $x_2$. La mitad occidental de plano contiene dos chiqueros $x_1$ e $x_2$, lo que puede poner un paraíso allí. Lo mismo es cierto para la mitad oriental de plano. Por lo tanto: $p(3)=2$.
- Para $n=4$, Cortar el plano a dos medio-planos mediante una línea vertical a través de $x_2$. Poner un paraíso en la mitad occidental-plano a través de la $x_1$ e $x_2$. En la mitad oriental de plano, de la orden de 3 de paraísos verticalmente en un orden creciente de sus valores de y y de corte para los dos trimestre-planos mediante un horiznotal línea a través de $y_2$. Cada trimestre el plano contiene 2 de abastecimiento de modo que usted puede tener una sola plaza en cada uno. Por lo tanto: $p(4)=3$.
- Para $n=5$, Cortar el plano a dos medio-planos mediante una línea vertical a través de $x_3$. Cortar las dos de la mitad de los aviones de a dos cuartos de aviones de cada uso de líneas horizontales. Cada trimestre el plano contiene 2 de abastecimiento (algunos de ellos en el límite), de modo que usted puede poner un paraíso en cada trimestre el plano. Por lo tanto: $p(5)=4$.
Este corte esquema no funciona al $n>5$, porque si terminamos con 3 chiqueros en un quarterplane, podría ser imposible tener 2 paraísos.
Por otro lado, en todos los casos que he examinado, siempre me las arreglé para encontrar a $n-1$ paraísos.
Así que la pregunta es: ¿es siempre posible tener $n-1$ paraísos, para cada $n$? Si es así, ¿cómo? Si no, ¿cuál es el mínimo?
TRABAJOS ANTERIORES:
Hace varios meses publiqué una pregunta similar en matemáticas.SÍ, con una importante diferencia: en lugar de un infinito desierto, había un número finito (plaza) pastel (es decir, todos los puntos y plazas deben estar dentro de un gran predefinidos cuadrado).
Con la ayuda de una respuesta desde el prof. Boris Bukh, me las arreglé para probar un límite superior de: $$p(n) \leq \lceil{n \over 2}\rceil - 1$$ The proof was by constructing a set of $n=2k$ points, that are organized such that it is not possible to put more than $p=k-1$ squares. The following figures illustrate the construction for $k=6$:
Más tarde también demostró un límite inferior de: $$ p(n) \geq {(n+2) \over 6} \ \ \ \ \ [n \geq 2]$$ La prueba fue mediante la descripción de un algoritmo recursivo que, dado un cuadrado con $n$ puntos, se divide el cuadrado de 4 plazas más pequeñas, y pone paraísos por separado en cada uno de ellos.
Ahora estoy tratando de adaptar estos resultados para el infinito desierto caso.
El límite superior de la construcción fundamentalmente se basa en la suposición de que el pastel está delimitado en al menos dos adyacentes direcciones. Se puede trabajar en un cuarto plano, pero no en un desierto sin límites ($\Bbb R^2$).
(En un medio plano, una construcción similar conduce a un límite superior de $p(n) \leq \lceil{2(n-1) \over 3}\rceil$).
El límite inferior algoritmo, obviamente, trabajar en un infinito desierto, sin embargo, después de sólo una sola iteración, vamos a tener 4 trimestre-aviones, y por lo tanto el límite inferior no va a ser mucho mejor que en el acotado de un pastel de caso.
