¿Un conjunto aleatorio de puntos en el plano contiene un gran polígono convexo vacío?

Question

Supongamos que elijo $n$ puntos uniformemente al azar desde el cuadrado unitario $[0,1]\times [0,1]$, obteniendo un conjunto de puntos $S=\{p_1,\ldots, p_n\}\subset [0,1]\times [0,1]$. Entonces $S$ puede contener subconjuntos que abarcan un polígono convexo vacío. Por ejemplo, en la ilustración a continuación, tenemos un polígono convexo vacío con $6$ esquinas. Un polígono está "vacío" si no contiene otro punto de $S$. Algunos cascos convexos pueden tener muchas esquinas, otros menos. Estoy interesado en el comportamiento asintótico de este fenómeno. Con este fin, sea

$$ f(S)= \max \{|T|:T\subseteq S\text{ y }T\text{ es convexo y } S\cap \text{conv}(T)=T\}$$

Pregunta. ¿Cómo crece la esperanza $\mathbb E[f]$ a medida que $n\to\infty$?

Conjetura. $\mathbb E[f]=\Theta(\sqrt{n})$, debido al paradoxo de cumpleaños.

Creo que esta es una pregunta del tipo Teoría de Ramsey, pero no estoy equipado para responderla. Estaría feliz con ya sea un límite inferior o un límite superior, o indicaciones para encontrarlos.

Answer 1

No, solo hay pequeños polígonos convexos vacíos

@BillyJoe ha descubierto que Balogh, Gonzalez-Aguilar y Salazar (1) resolvieron esta pregunta en 2012. Mostraron que un conjunto aleatorio de puntos contiene, en promedio, un polígono convexo vacío de tamaño

$$\mathbb E[f]=\Theta\left(\frac{\log n}{\log\log n}\right)$$ También muestran que con alta probabilidad, este es el tamaño del más grande, es decir, los valores atípicos no influyen mucho en el promedio (por supuesto, existen valores atípicos: podrías distribuir $n$ puntos a lo largo de un círculo, pero tales configuraciones son aparentemente muy raras).

Permítanme dar una exposición de su argumento sorprendentemente simple de que es probable que encuentres un polígono convexo vacío tan grande.

---

Primero: La probabilidad de que $r$ puntos formen un polígono convexo es conocida (¡exactamente! debido a Valtr [2]), si los puntos se extraen de cualquier paralelogramo, es decir, $$ \mathbb P[r \text{ puntos son convexos}]=\left(\frac{\binom{2r-2}{r-1}}{r!}\right)^2$$

Ellos imaginan ahora que obtenemos repetidamente dibujar $r$ puntos al azar de un paralelogramo; si tenemos un polígono convexo de $r$ lados, el experimento es exitoso; de lo contrario, repetimos el experimento desde cero. Entonces preguntan: ¿Cuántas veces tendríamos que repetir este experimento, dibujando $r$ puntos cada vez, antes de ver un polígono con $r$ lados? Resulta que elegir $n$ que satisface $r=\frac{\log(n)}{2\log\log(n)}$ hace el truco: entonces hacemos $n/r$ experimentos independientes antes de ver nuestro primer polígono convexo de $r$ lados, dibujando un total de $n$ puntos en todos los experimentos. Así que tenemos nuestro límite.

Muy bien, pero esto solo funcionaría si tuviéramos $n/r$ paralelogramos disjuntos con los que trabajar. Pero no lo tenemos, porque en nuestro entorno dibujamos todos nuestros puntos desde el cuadrado $[0,1]\times [0,1]$, por lo que nuestros "experimentos" de $n/r$ no son independientes. ¿Cómo lo solucionamos?

Los autores usan un truco ingenioso aquí. Es decir, supongamos que hemos dibujado $n$ puntos al azar, y supongamos sin pérdida de generalidad que ninguno de ellos está en una línea vertical. Entonces podemos agrupar los puntos de izquierda a derecha en grupos de $r$ puntos, de modo que el cuadrado se divida en rectángulos largos de $n/r$ puntos, como se muestra en la ilustración a continuación.

Estos puntos están en rectángulos no superpuestos. Además, condicionado al hecho de que un rectángulo dado contiene $r$ puntos, han sido dibujados de forma uniforme al azar desde ese rectángulo, ¡así que nuestro límite se aplica de todos modos!

Q.E.D.

---

Luego demuestran que este es de hecho el más grande polígono que probablemente encontrarás, pero a través de un argumento más complicado, que dejo para que el lector explore.

Quiero hacer notar que mi conjetura de $\mathbb E [f]=\Theta(\sqrt n)$ era exponencialmente más alta que la respuesta real; un gran error. Había supuesto que el polígono convexo vacío más grande podría contener aproximadamente tantos vértices como la envolvente convexa de los $n$ puntos, lo que pensé que serían aproximadamente $\approx \sqrt n$ puntos, ya que esa es la longitud de cada lado. Esta era la dirección correcta, excepto que esta estimación también estaba muy lejos de la realidad, ya que al parecer la mayoría de los puntos cerca del borde no están en la envolvente convexa después de todo, de hecho solo $\Theta(\log n)$ puntos conforman la envolvente, demostrado por Renyi y Sulanke [3]. Una vez más, estuve equivocado por una magnitud exponencial.

Me parece que la estimación del número de vértices que uno probablemente encuentra, $\geq \log(n)/2\log\log n$, probablemente se pueda mejorar (por un factor constante solamente, ya que el límite es ajustado asintóticamente), considerando un argumento más complejo que intente colocar más puntos en cada rectángulo. Actualmente, los límites superiores e inferiores de Balogh et al. difieren en un factor de 320, es decir, mostraron que con alta probabilidad, con $r$ el más grande polígono convexo vacío, $$\frac{\log n}{2\log \log n}\leq r\leq 160\frac{\log n}{\log\log n}$$ También parece que no se han hecho intentos para reducir esta brecha, así que cualquier entusiasta de la teoría de Ramsey tiene trabajo por delante.

Referencias

(1) Balogh, József; González-Aguilar, Hernán; Salazar, Gelasio, Grandes orificios convexos en conjuntos de puntos aleatorios, Comput. Geom. 46, No. 6, 725-733 (2013). ZBL1271.52003.

(2) Valtr, P, Probabilidad de que (n) puntos aleatorios estén en posición convexa, Discrete Comput. Geom. 13, No. 3-4, 637-643 (1995). ZBL0820.60007.

(3) Rényi, Alfréd; Sulanke, R., Sobre la envolvente convexa de (n) puntos elegidos al azar, Z. Wahrscheinlichkeitstheor. Verw. Geb. 2, 75-84 (1963). ZBL0118.13701.