Rectángulo más grande no tocar ninguna de rock en un campo cuadrado

Question

Usted quiere construir una casa rectangular con un área máxima. Se le ofrece un campo cuadrado de área 1, en el que va a construir la casa. El problema es que hay $n$ piedras esparcidas en lugares desconocidos por todo el campo. Las rocas son inamovibles, y no se puede construir sobre las rocas. ¿Cuál es la mayor área de un rectángulo que se puede construir, en el peor de los casos?

Formalmente: vamos a $S_n$ ser un conjunto de $n$ puntos en la plaza de la unidad. Definir $\textrm{MaxArea}(S_n)$ como el área máxima de un eje paralelo rectángulo en la unidad de la plaza que no contiene, en su interior, cualquier punto en $S$. Definir:

$$\textrm{MinMaxArea}(n) = \inf_{S_n} (\textrm{MaxArea}(S_n))$$

donde el infimum es en todos los posibles conjuntos de $S_n$ $n$ puntos. ¿Cuáles son las buenas límites en $\textrm{MinMaxArea}(n)$?

EJEMPLO: En la imagen de abajo, la unidad de la plaza se escala a un 100 por 100 de la plaza. Hay $n=100$ rocas. Al parecer, la mayor rectángulo que no contiene ningún tipo de rocas en su interior se encuentra un rectángulo como ABCD, cuya área es de $.06\times .58$, que es aproximadamente de $\frac{1}{4\sqrt{n}}$, así:

$$\textrm{MinMaxArea}(n) \leq \frac{1}{4\sqrt{n}}$$

Hay otra disposición de las rocas en la que el rectángulo más grande es más pequeño?

Answer 1

Tuve que lidiar con este problema hace mucho tiempo. Aquí están mis resultados. Todavía están sin publicar, así que apoyo la idea de escribir un documento conjunto.

Answer 2

Permítanme acortar MaxArea ($S_n$) $M(S_n)$ por comodidad, y deje $M(n) = \inf_{S_n} M(S_n)$ ser MinMaxArea (esta es la sobrecarga de la notación, pero espero que no haya confusiones).

A continuación, $M(S_n) \le D(S_n)$ donde $D(S_n)$ es la clásica de la función de discrepancia:

$$ D(S_n) = \sup_R \left|\frac{|S_n \cap R|}{n} - \mathrm{área}(R) \right|, $$ donde el supremum está sobre el eje paralelo rectángulos en $[0,1]^2$. Hay muy pocas construcciones de $n$-punto de conjuntos de $S_n$ que $D(S_n) = O(\log(n)/n)$. Un ejemplo es $$ S_n = \left\{ \left(\frac{i}{n}, i\sqrt{2} \bmod 1\right) \right\}_{i = 0}^{n-1}. $$ Otra es la de van der Corput conjunto. Esto demuestra que $M(n) = O(\log(n)/n)$.

Tan lejos como los límites inferiores de ir, es conocido que el anterior límite en $D(n)$ es ajustado, es decir,$D(n) = \Omega(\log(n)/n)$.

Sin embargo, incluso en el mejor de los límites son posibles si trabajamos directamente con $M(n)$. Deje $n(\epsilon)$ ser el tamaño de la más pequeña de punto de ajuste $P$ tal que $M(P) \le \epsilon$ (esto se llama un $\epsilon$-net). Entonces es conocido que $n(\epsilon) = O(\frac{1}{\epsilon}\log \log \frac{1}{\epsilon})$, lo que implica que $M(n) = O(\log \log(n)/n)$.

(Tenga en cuenta que el $\epsilon$-redes de literatura trabaja generalmente con intervalo discreto espacios, pero debido a los límites en las $n(\epsilon)$ están en función de $\epsilon$ solamente, se puede tomar arbitrariamente un fino discretos aproximación de $[0,1]^2$.)