Considere $n$ círculos de radio variable $r_1,\ldots, r_n$ que empaquetan dentro de un círculo fijo de radio unitario. En otras palabras, todos $n$ Los círculos de radio variable están contenidos en el círculo de radio unitario y sus interiores tienen intersecciones vacías. El gráfico de tangencia de un empaquetamiento comprende $n+1$ vértices, uno por cada círculo, y aristas entre vértices si los círculos correspondientes son tangentes.
Conjetura: en un empaquetamiento que maximiza $r_1+\cdots +r_n$ , el gráfico de tangencia correspondiente es plano y triangulado.
Esta conjetura parece estar relacionada con el teorema de empaquetamiento de círculos de Koebe-Andreev-Thurston. Este último afirma que para cada grafo plano triangulado existe un empaquetamiento circular correspondiente del tipo descrito y que este empaquetamiento es único hasta transformaciones conformes. Aunque resulta que el teorema KAT puede proporcionar algunas ideas para demostrar la conjetura, creo que ocurre algo más. Por ejemplo, la función objetivo radio-suma no es invariante conformacional.
Tengo buenas pruebas numéricas en apoyo de esta conjetura. Las configuraciones óptimas que he encontrado hasta $n=20$ todos tienen gráficos triangulados. Estoy publicando esto en MO porque también tengo algo que parece que puede estar "cerca" de una prueba. Tal vez alguien pueda cerrar la brecha o convencerme de que la brecha es en realidad un abismo sin fondo - ¡cualquiera de las dos cosas sería útil!
Esta es mi estrategia de prueba:
-
Utilice la convexidad para demostrar que una configuración óptima maximiza el número de aristas en el gráfico de tangencia.
-
Utilice el teorema de Euler para demostrar que un grafo de tangencia que maximiza el número de aristas es triangulado.
Se trata de un problema de optimización con restricciones en $\mathbb{R}^{3n}$ . Consideremos la restricción que se aplica a los círculos 1 y 2: $(x_1-x_2)^2+(y_1-y_2)^2 \ge (r_1+r_2)^2$ . Este tipo de restricción se denomina "convexa inversa" (la región factible es el complemento de un conjunto convexo abierto). Las regiones factibles en problemas de convexidad inversa (intersección de complementos de conjuntos abiertos) pueden ser bastante complejas, incluso pueden no estar conectadas. Por otro lado, tienen una propiedad muy interesante cuando maximizamos una función convexa: siempre se puede encontrar un óptimo en un "vértice" de la región factible. En un problema convexo inverso en $\mathbb{R}^{N}$ un vértice es un punto de la región factible en el que al menos $N$ de las restricciones son igualdades. Podemos considerar los problemas convexos inversos como una generalización de la programación lineal que hereda todas las buenas propiedades locales.
La existencia de un optimizador global requiere que la región factible no sea vacía y sea compacta. Esto no es un problema para el problema de empaquetamiento circular, ya que podemos dejar que los radios abarquen todos los números reales y añadir restricciones convexas inversas $r_1\ge 0,\ldots,r_n\ge 0$ .
El lector avisado ya se habrá dado cuenta de que no todas las restricciones del problema de empaquetamiento circular son convexas inversas. Las restricciones que se aplican al círculo unitario fijo tienen un sentido erróneo de la desigualdad, por ejemplo $x_1^2 + y_1^2 \le (1-r_1)^2$ . Se puede intentar solucionar este problema sustituyendo el círculo de unidades fijas por un círculo regular. $M$ -gon y tomando el límite (en cierto sentido) de grandes $M$ . Esto tiene dos buenas consecuencias. En primer lugar, la optimización es ahora realmente convexa inversa (restricción de medio plano para cada lado del polígono) y por lo tanto hay un optimizador donde exactamente $3n$ están activas (en su valor de igualdad). Para ver la segunda característica interesante tenemos que hacer algunas cuentas.
El gráfico de tangencia presenta una nueva característica cuando el círculo fijo se sustituye por un círculo regular $M$ -gon: ya no es simple porque puede tener aristas dobles entre las circunferencias de radio variable y el polígono (siempre que una circunferencia sea tangente a aristas adyacentes del polígono). Sea el número de circunferencias con tangencias dobles $D$ . Si $E$ y $F$ son el número de aristas y caras del grafo, y $\tilde{E}$ y $\tilde{F}$ son estas cantidades cuando las aristas duplicadas se fusionan en aristas simples, entonces $E=\tilde{E}+D$ y $F=\tilde{F}+D$ . Dado que nuestro gráfico tiene $n+1$ vértices, y la programación convexa inversa nos dice que existe un óptimo con $E=3n$ tangencias, el teorema de Euler da $n+1-3n+F=2$ o $F=2n+1$ . Por lo tanto, tenemos las siguientes fórmulas para el "grafo reducido" después de fusionar las aristas dobladas: $\tilde{E}=3n-D$ , $\tilde{F}=2n+1-D$ . El grafo reducido es simple y plano y satisface $2\tilde{E}\ge 3\tilde{F}$ donde la igualdad implica que el grafo es triangulado. Utilizando nuestras fórmulas esta desigualdad se convierte en $D\ge 3$ .
El resultado de este análisis es que las configuraciones óptimas en el $M$ -gon tienen al menos 3 circunferencias con doble tangencia, y que el grafo reducido está triangulado cuando se cumple este mínimo. El número 3 es interesante. Creo que corresponde al hecho de que las transformaciones conformacionales se fijan especificando 3 puntos en el límite de la región (el $M$ -gon) donde se mapean los círculos. Sacrificar la simetría del círculo fijo valió la pena porque permitió que el problema de optimización tuviera soluciones discretas (cuya existencia se deduce de la programación convexa inversa).
Hay dos lagunas en la prueba. ¿Cómo tomamos los resultados para el $M$ -gon y mediante algún proceso límite demostrar un teorema sobre el círculo? En segundo lugar, ¿cómo demostramos $D=3$ ? Configuraciones óptimas con $D>3$ se vuelven más improbables a medida que $M$ se hace grande porque en ese caso más del número mínimo de restricciones activas surgen de tangencias dobles. Después de todo, el par de restricciones en una tangencia doble se degenera en $M=\infty$ .
Creo que la conjetura es cierta para la clase de funciones objetivo $r_1^p+\cdots + r_n^p$ donde $1\le p < 2$ . El caso $p\ge 2$ no es interesante porque los óptimos degeneran en un único círculo que llena completamente el círculo fijo, el resto tiene radio cero.
