Puede un conjunto discreto de el plano de densidad uniforme se cruzan todos los triángulos grandes?

Question

Sea S un subconjunto discreto de la distancia Euclídea del plano tales que el número de puntos en un gran disco es aproximadamente igual al área del disco. ¿El complemento de S necesariamente contienen los triángulos de arbitrariamente grande de la zona?

Answer 1

Edit: La respuesta a continuación es algo obsoleto, debido a la reciente papel de Noga Alon, donde se establece el primer no-trivial de los límites inferiores de fuerte epsilon-redes.

La vieja respuesta: Esta respuesta utiliza parte de la terminología de la geometría discreta. Las definiciones, y más material de fondo se puede encontrar en, por ejemplo, "Discretos de la geometría" de Jiří Matoušek los capítulos 9 y 10. Menos presentación completa puede ser consultada sin ir a la biblioteca.

Si uno cae el requisito de que tiene que tener asintótica de la densidad, y sólo pide para el conjunto a tiene una densidad constante en algunos de los grandes (pero fijo) de la bola, y restringe el uso de los triángulos para vivir dentro de la pelota, el problema no se convierta en mucho más fácil. En ese caso el problema pide la construcción de un 1/r-net de tamaño S(r) para la familia de todos los triángulos con respecto a la medida de Lebesgue en [0,1]^2 (o, equivalentemente, para la construcción de 1/r-net para una cuadrícula {1,..,N}x{1,...,N} para la gran N). El límite superior de r*registro r en el tamaño de la red de la siguiente manera a partir de la finitud de Vapnik Chervonenkis dimensión. Para la gama general de espacios finitos VC dimensión de la logarítmica del factor de es necesario. Sin embargo, hay por ahora varios resultados que quitar o reducir el logarítmica del factor "geométricamente interesante gama de espacios" (como muestra, aquí es un resultado de eje paralelo cajas). Desafortunadamente, hasta donde yo sé, estos desarrollos no incluyen el espacio de triángulos en el plano (yo podría estar equivocado; usted debe verificar con uno de los expertos).

Mostrando la no-existencia de pequeñas 1/r-redes para este problema, ciertamente, es abierto, y es probable que esté duro. El único que actualmente se conoce el límite inferior de 1/r-redes para cualquier problema geométrico todo cuanto hay en mi papel con Matoušek y Nivasch, y es para la familia de todos los conjuntos convexos. Sin embargo, en lugar de una rejilla de {1,...,N}x{1,...,N} que aparece en este problema, la construcción es una especie de muy estirado de la cuadrícula.

Answer 2

Esta pregunta es exasperante. Creo que he avanzado un poco, y me gustaría escuchar los pensamientos del otro. Por lo tanto, estoy haciendo este post un wiki de la comunidad:

---

Primero de todo, cualquier triángulo de área contiene un rectángulo de área de A/2. Prueba: deja que el triángulo ABC, con CA el lado más largo. Sean P y Q sean los puntos medios de AB y BC, y dejar que R y S sean los pies de las perpendiculares de P y Q de CA. Luego PQSR es un rectángulo de área requerida. Por el contrario, un rectángulo de área contiene un triángulo de área de A/2. Así que en lugar de preguntar si hay grandes rectángulos en el complemento.

Esto es conveniente porque la especificación de un triángulo consiste en 6 parámetros, mientras que la especificación de un rectángulo tiene sólo 5. Así que esto de los recortes nuestro espacio de búsqueda abajo de una dimensión. Lo que me parece más conveninent los parámetros de un rectángulo a ser la longitud del lado más largo, L, el área, A, el ángulo del lado más largo, $\theta$, y uno de los vértices $(x,y)$. Voy a llamar al tipo del rectángulo $(L, A, \theta)$, olvidando la traducción de los parámetros.

---

Ahora tengo una hipótesis de solución, aunque no tengo idea de cómo probar que funciona. Yo llamo a esto el girasol de configuración, ya que fue inspirado por el patrón de los floretes en el centro de un girasol.

Deje que $\tau$ ser la proporción áurea. Considerar la secuencia de los puntos $(\sqrt{k} \cos(2 \pi \tau k), \sqrt{k} \sin(2 \pi \tau k))$. Un círculo de radio $R$ todo $0$ $R^2$ puntos, y tiene zona de $\pi R^2$, por lo que la densidad es la derecha.

¿Por qué creo que esto es razonable? Hay una hermosa propiedad de la proporción áurea: si nos fijamos en la secuencia de $k \tau, (k+1) \tau, (k+2) \tau, ..., \ell \tau$ en $\mathbb R/\mathbb Z$, entonces la brecha más grande entre dos consecutivos ángulos es de $\dfrac\tau{\ell-k}$. Así múltiplos de $2 \pi \tau$ están muy bien distribuidas alrededor del círculo unitario. Esto lo aprendí desde el Volumen 2 de el Arte de la Programación de ordenadores; voy a tratar de encontrar una referencia más tarde si nadie más lo hace.

No tengo una estrategia pero para probar que el de girasol patrón no contienen grandes triángulos (o rectángulos). Pero, donde cada vez que intento poner una, la heurística indican que este equidistribución de los ángulos destruye mí.

---

Mi primera estrategia, con el objetivo de probar un "no", fue la superposición de varias celosías que fueron todas las rotaciones de cada uno de los otros. Vamos a fijar en $Una$ de una vez por todas, nuestro objetivo es excluir un rectángulo de tamaño $A$. Yo en primer lugar, a ver cuando un entramado podría contener un rectángulo de tipo $(L, A, \theta)$.

Traducir el rectángulo de modo que uno de los lados cortos toques $(0,0)$. Entonces el rectángulo que contiene una circular en la cuña de radio $L$ y el ángulo de aproximadamente $A/L^2$ sin celosía puntos. En otras palabras, no hay $(p,q)$ con $\sqrt{p^2+q^2} \le L$ y $|\theta \bronceado^{-1}(p/q)| \le c\cdot A/L^2$, donde $c$ es una constante que no se han calculado.

Ahora hay un montón de molestias, que tiene que ver con la presencia de los $bronceado^{-1}$ y el hecho de que las personas que hacen Diophatine aproximación general pide $q$ a ser pequeño, no $\sqrt{p^2+q^2}$. Pasando por encima de todos los detalles, el conjunto de $\theta$'s para que un rectángulo existe debe ser algo como la unión de todos los intervalos en la $L$-ésima secuencia de Farey cuya longitud es mayor que $A/L^2$. La heurística a mi me da que el tamaño de este es de $c/Una$ para $c$ a (diferentes) constante que no he calculado.

Así, una de las redes no puede salvarme. La anterior sugiere que, por cada $L$, habrá un positivo longitud de $\theta$'s para que los rectángulos de tipo $(L, A, \theta)$ existir. Por supuesto, ya se sabía que un solo entramado no podía trabajar.

¿Qué acerca de dos celosías, girado por algunos phi? Creo que todavía perder. Como $L$ crece, el conjunto de la teta de la que el trabajo es de tamaño $1/$, pero se vuelve más y más hacia fuera. Finalmente, yo esperaría que contendría dos puntos que se diferencian por su phi. Esta parte es muy nonrigorous, aunque. En particular, no estoy seguro de si podría ser capaz de guardar las cosas para algunos muy especial phi.

Que trata de lo lejos que he llegado. He probado algunas otras ideas, pero no llegar a ninguna parte. Ni siquiera estoy seguro de que la respuesta que yo creo que es correcto.

Answer 3

Sobre el niza de la construcción David Speyer: tengo la impresión de que no funciona. Razón: Hay grandes regiones donde la configuración se parece mucho a un entramado con bastante densidad grande (no cerca de puntos). Esta región contiene así triángulos grandes (por supuesto uno puede reemplazar triángulos conjunto convexo o por rectángulos, esto no cambia el problema). Me hizo bastante grueso y rápido cálculo de lo que parece demostrar que no de hecho son las regiones que figuran en arbitrariamente grandes discos en los que los puntos del conjunto son en su mayor parte a distancia \epsilon (arbitrariamente pequeño positivo \epsilon) de los puntos de un denso entramado. Este cálculo (si es correcto) implica fácilmente la existencia de arbitrariamente grandes triángulos en el complemento.

Sobre la historia del problema: no tengo conocimiento de que se ha considerado en el presente formulario. He escrito un documento "Universal Convexo Cubiertas" que aparece en el Boletín de la LMS (una copia en el arXiv) donde puedo construir un conjunto con R^2 log(R) puntos de (Euclideean) la norma en la mayoría de los R, que cruza todos los triángulos (o, equivalentemente, conjuntos convexos) de área suficientemente amplia. (El documento contiene en realidad una construcción de dimensiones arbitrarias). Yo soy así de curioso si uno puede deshacerse de el logaritmo. De hecho, creo que el logaritmo puede ser mejorado para algunos de los más pequeños poco a poco aumentar la función, pero yo estaría muy sorprendido por la existencia de un conjunto con densidad uniforme.

Answer 4

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

Hay un papel que demuestre que no hay unión de un número finito de celosías pueden trabajar. Voy a tratar de recordar lo que es. Recuerdo que es un resultado de Mahler.

Añadido posterior: creo que fue de Mahler selección teorema. Tal vez la pista suficiente para que alguien reconstruir la prueba (que me parece recordar que no era enormemente difícil).

Answer 5

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

Sin embargo, a diferencia de Heilbronn del problema en el triángulo que queremos no está obligado a tener a tres de los n puntos dados como sus vértices; por ejemplo, si n puntos fueron colocados juntos en el disco no habría gran triángulo que tiene tres de ellos como vértices, pero no lo haría existen grandes vacíos de triángulos. Yo lo hice en menos de encontrar un papel que es una especie de con relación a esto: En un Triángulo con el Área Máxima en un Plano de Conjunto de puntos, Hisono et al 2005, demuestran que existen conjuntos de n puntos para los cuales la relación de áreas de los más grandes vacíos triángulo con los tres puntos como vértices y el casco convexo de todos los vértices es O(1/n).

Por el camino, es fácil definir conjuntos de puntos tales que no hay un gran vacío triángulo que contiene el origen: coloque un anillo de 2^k puntos en radio 2^k, para k = 1, 2, 3, 4, ... La densidad de puntos dentro de cualquier no constante de la zona del disco entonces será superior e inferior delimitada por un número constante de veces el área del disco, y por la adición de otros de los puntos que uno puede hacer el superior y el límite inferior constantes tan cerca como uno desea para cada uno de los otros. Así que de alguna manera, si los triángulos grandes existir siempre, a veces tienen que estar lejos del origen.