43 votos

¿Puede un conjunto discreto del plano de densidad uniforme intersecar todos los triángulos grandes?

Sea S un subconjunto discreto del plano euclidiano tal que el número de puntos de un disco grande es aproximadamente igual al área del disco. ¿El complemento de S contiene necesariamente triángulos de área arbitrariamente grande?

(Añadido en julio de 2021:) Recientemente me he enterado de que esto es El problema de Danzer . Un conjunto Danzer ( https://en.wikipedia.org/wiki/Danzer_set ) es un contraejemplo. Aparentemente no es tan conocido, aunque el comienzo de la respuesta de Gowers sugiere que ha oído hablar de él.

13voto

ninegrid Puntos 213

Editar: La respuesta que aparece a continuación es algo obsoleta, debido a la reciente documento de Noga Alon donde establece los primeros límites inferiores no triviales para redes épsilon fuertes.

Respuesta antigua: Esta respuesta utiliza cierta terminología de la geometría discreta. Las definiciones y más material de fondo se pueden encontrar, por ejemplo, en "Discrete geometry" de Jiří Matoušek, capítulos 9 y 10. Se puede consultar una introducción menos exhaustiva sin ir a la biblioteca .

Si se suprime el requisito de que el conjunto tenga una densidad asintótica, y se pide simplemente que el conjunto tenga una densidad constante en alguna bola grande (pero fija), y se restringe que los triángulos vivan dentro de esa bola, el problema no es mucho más fácil. En ese caso, el problema pide la construcción de una red 1/r de tamaño O(r) para la familia de todos los triángulos con respecto a la medida de Lebesgue en [0,1]^2 (o, de forma equivalente, la construcción de una red 1/r para una cuadrícula {1,...N}x{1,...,N} para N grande). El límite superior de r*log r en el tamaño de la red se deriva de la finitud de la dimensión de Vapnik Chervonenkis. Para los espacios de rango general con dimensión VC finita, el factor logarítmico es necesario. Sin embargo, hay por ahora varios resultados que eliminan o reducen el factor logarítmico en "espacios de rango geométricamente interesantes" (como muestra, aquí es un resultado para cajas paralelas al eje). Desgraciadamente, por lo que sé, estos desarrollos no incluyen el espacio de los triángulos en el plano (puede que me equivoque; deberías consultarlo con alguno de los expertos).

Demostrar la inexistencia de redes pequeñas de 1/r para este problema está ciertamente abierto, y probablemente sea difícil. El único límite inferior conocido actualmente para 1/r-redes para cualquier problema geométrico se encuentra en mi documento con Matoušek y Nivasch y es para la familia de todos los conjuntos convexos. Sin embargo, en lugar de una rejilla {1,...,N}x{1,...,N} que aparece en este problema, la construcción es una especie de rejilla muy estirada.

9voto

sickgemini Puntos 2001

Esta pregunta es exasperante. Creo que he hecho algunos progresos, y me gustaría escuchar las opiniones de los demás. Por lo tanto, estoy haciendo este post un wiki de la comunidad:


En primer lugar, cualquier triángulo de área A contiene un rectángulo de área A/2. Prueba: sea el triángulo ABC, siendo AC el lado más largo. Sean P y Q los puntos medios de AB y BC, y sean R y S los pies de las perpendiculares de P y Q a AC. Entonces PQSR es un rectángulo del área requerida. A la inversa, un rectángulo de área A contiene un triángulo de área A/2. Por tanto, podemos preguntarnos si hay rectángulos grandes en el complemento.

Esto es conveniente porque especificar un triángulo implica 6 parámetros, mientras que especificar un rectángulo sólo tiene 5. Así que esto reduce nuestro espacio de búsqueda en una dimensión. Los parámetros más convenientes para un rectángulo son la longitud del lado más largo, L, el área, A, y el ángulo del lado más largo, $\theta$ y uno de los vértices $(x,y)$ . Llamaré al tipo de rectángulo $(L, A, \theta)$ olvidando los parámetros de traducción.


Ahora tengo una solución conjetural, aunque no tengo idea de cómo demostrar que funciona. La llamo la configuración del girasol, porque está inspirada en el patrón de floretes en el centro de un girasol.

Dejemos que $\tau$ sea la proporción áurea. Consideremos la secuencia de puntos $(\sqrt{k} \cos(2 \pi \tau k), \sqrt{k} \sin(2 \pi \tau k))$ . Un círculo de radio $R$ alrededor de $0$ contiene $R^2$ puntos, y tiene un área $\pi R^2$ así que la densidad es correcta.

¿Por qué creo que esto es razonable? Hay una magnífica propiedad de la proporción áurea: si se observa la secuencia $k \tau, (k+1) \tau, (k+2) \tau, ..., \ell \tau$ en $\mathbb R/\mathbb Z$ entonces la mayor distancia entre dos ángulos consecutivos cualesquiera es $\dfrac\tau{\ell-k}$ . Así que los múltiplos de $2 \pi \tau$ están muy bien distribuidos alrededor del círculo de la unidad. Esto lo aprendí del Volumen 2 del Arte de la Programación de Ordenadores; intentaré encontrar una referencia más tarde si nadie lo hace.

Todavía no tengo una estrategia para demostrar que el patrón del girasol no contiene triángulos (o rectángulos) grandes. Pero, siempre que intento colocar uno, la heurística me indica que esta equidistribución de ángulos me destroza.


Mi primera estrategia, con el objetivo de demostrar un "no", fue superponer varios entramados que eran rotaciones unos de otros. Fijemos $A$ de una vez por todas, nuestro objetivo es excluir un rectángulo de tamaño $A$ . Primero me propuse ver cuándo un entramado podía contener un rectángulo de tipo $(L, A, \theta)$ .

Traslada el rectángulo para que uno de los lados cortos toque $(0,0)$ . Entonces el rectángulo contiene una cuña circular de radio $L$ y el ángulo aproximadamente $A/L^2$ sin puntos de rejilla. En otras palabras, no hay $(p,q)$ con $\sqrt{p^2+q^2} \le L$ y $|\theta - \tan^{-1}(p/q)| \le c\cdot A/L^2$ , donde $c$ es una constante que no he calculado.

Ahora hay un montón de molestias, que tienen que ver con la presencia de ese $tan^{-1}$ y el hecho de que la gente que hace la aproximación de Diophatine suele pedir $q$ ser pequeño, no $\sqrt{p^2+q^2}$ . Pasando por alto todos los detalles, el conjunto de $\theta$ para los que existe dicho rectángulo debería parecerse a la unión de todos los intervalos del $L$ -a secuencia de Farey cuya longitud es mayor que $A/L^2$ . La heurística me da que el tamaño de esto es $c/A$ para $c$ una constante (diferente) que no he calculado.

Así que una celosía no puede salvarme. Lo anterior sugiere que, por cada $L$ habrá un conjunto de longitudes positivas de $\theta$ para los que los rectángulos de tipo $(L, A, \theta)$ existe. Por supuesto, ya sabíamos que una red única no podía funcionar.

¿Qué pasa con dos celosías, rotadas por algún phi? Creo que sigo perdiendo. Como $L$ crece, el conjunto de theta's que funcionan se mantiene de tamaño $1/A$ pero cada vez se extiende más. Al final, se espera que contenga dos puntos que se diferencian por phi. Sin embargo, esta parte es muy poco rigurosa. En particular, no estoy seguro de si podríamos guardar las cosas para algún phi muy especial.

Hasta ahí he llegado. Intenté otras ideas, pero no llegué a ninguna parte. Ni siquiera estoy seguro de cuál es la respuesta correcta.

8voto

bneely Puntos 346

Acabo de ver esta pregunta. Es un conocido problema abierto en geometría discreta. Por desgracia, no recuerdo cómo se llama.

Hay un artículo que demuestra que ninguna unión de retículos finitos puede funcionar. Intentaré recordar cuál es. Recuerdo que utilizaba un resultado de Mahler.

Añadido más tarde: Creo que era el teorema de selección de Mahler. Tal vez sea una pista suficiente para que alguien reconstruya la prueba (que creo recordar que no era enormemente difícil).

4voto

Ashley Clark Puntos 6806

Respecto a la bonita construcción David Speyer: tengo la impresión de que no funciona. Razón: Hay grandes regiones en las que la configuración se parece mucho a un entramado con una densidad bastante grande (no hay puntos cercanos). Esta región contiene por tanto grandes triángulos (por supuesto se pueden sustituir los triángulos por conjuntos convexos o por rectángulos, esto no cambia el problema). Hice un cálculo bastante grueso y rápido que parece mostrar que hay hay regiones contenidas en discos arbitrariamente grandes donde los puntos del conjunto están como máximo a la distancia \epsilon (para un valor positivo pequeño arbitrario \epsilon ) de los puntos de una red densa. Este cálculo (si es correcto) implica fácilmente la existencia de triángulos arbitrariamente grandes en el complemento.

En cuanto a la historia del problema: no me consta que se haya planteado en la forma actual. He escrito un artículo "Universal Convex Coverings" que aparece en el Boletín de la LMS (una copia está en el arXiv) donde construyo un conjunto con R^2 log(R) puntos de norma (euclidiana) a lo sumo R que interseca todos los triángulos (o equivalentemente, conjuntos convexos) de área suficientemente grande. (El artículo contiene de hecho una construcción para dimensiones arbitrarias). Por lo tanto, tengo curiosidad por saber si uno puede deshacerse del logaritmo. De hecho, creo que el logaritmo puede mejorarse a alguna función más pequeña y lentamente creciente, pero me sorprendería mucho la existencia de tal conjunto con densidad uniforme.

3voto

Flow Puntos 14132

Esto parece algo relacionado con el problema del triángulo de Heilbronn, que consiste en determinar el peor comportamiento del triángulo de área mínima determinado por un conjunto de n puntos en un disco unitario. En este caso, en lugar del triángulo más pequeño determinado por un conjunto de puntos, queremos el triángulo vacío más grande; creo que una versión equivalente de la pregunta es preguntar si, para todos los conjuntos de n puntos en el disco unitario, el triángulo vacío más grande tiene área O(1/n).

Sin embargo, a diferencia del problema de Heilbronn, no es necesario que el triángulo que queremos tenga tres de los n puntos dados como vértices; por ejemplo, si los n puntos se colocan cerca uno del otro dentro del disco, no habrá ningún triángulo grande que tenga tres de ellos como vértices, pero habrá otros triángulos grandes vacíos. Al menos he encontrado un artículo que está más o menos relacionado con esto: Sobre un triángulo con el área máxima en un conjunto de puntos planos Hosono et al. 2005, demuestran que existen conjuntos de n puntos para los que la relación entre las áreas del mayor triángulo vacío con tres de los puntos como vértices y el casco convexo de todos los vértices es O(1/n).

Por cierto, es fácil definir conjuntos de puntos tales que no haya ningún triángulo grande vacío que contenga el origen: coloque un anillo de 2^k puntos de radio 2^k, para k = 1, 2, 3, 4, ... La densidad de puntos dentro de cualquier disco de área no constante estará entonces limitada superior e inferiormente por una constante que multiplica el área del disco, y añadiendo otros puntos se puede hacer que las constantes de los límites superior e inferior se acerquen tanto como se desee. Así que, de alguna manera, si los triángulos grandes siempre existen, a veces deben estar lejos del origen.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X