Puntos y líneas en el plano

Question

¿Es un número real positivo $k\geq1$ existen tales que para todo conjunto finito $P$ de puntos en el plano (con la propiedad de que no hay tres puntos de $P$ se encuentran en una línea común y $|P|\geq3$ ), se puede elegir un subconjunto $Q$ de $P$ con $|Q| \geq |P|/k$ puntos y con la propiedad de que existen dos puntos diferentes $a$ y $b$ en $Q$ de manera que ninguna línea $\overline{(p,q)}$ a través de dos puntos diferentes $p,q$ de $Q\backslash\{a,b\}$ atraviesa el interior del segmento $(a,b)$ ?

Si tal número existe, ¿cuál es el número entero más pequeño $k$ ¿Realizando la propiedad?

Si se toma un conjunto $P=\{a,b,c\}$ con tres puntos, entonces puede establecer $P=Q$ ya que ninguna línea cruza el interior del segmento $(a,b)$ . Sin embargo, un contraejemplo para $k=1$ es la que ofrece Reid Barton a continuación.

Answer 1

Apostaría a que la respuesta a esta pregunta es que tal k no existe. Para construir un contrexample a cualquier k yo consideraría un cuadrado muy grande del tamaño Nk x Nk, N>>1 y tomaría todos los puntos enteros dentro de él. Ahora perturbe un poco todos estos puntos (Nk)^2 de tal manera que no haya 3 en una línea. Parece que esta configuración será contrexample para N grande. La razón para pensar así es que antes de que perterb esta configuartion para cada segmento ab hay aproximadamente por lo menos aproximadamente (Nk)^3 pares de puntos dentro del cuadrado tal que la línea los tira intersecan segmento dado. Parece que hay que tirar demasiados puntos.

Answer 2

No es lo mismo, pero para cada dos puntos a y b de P existe un subconjunto Q de P con |Q| = Ω(√|P|) de forma que o bien ninguna recta(p,q) que pase por dos puntos de Q cruza el segmento(a,b), o bien toda recta(p,q) cruza el segmento.

Para ver esto, primero observamos que borrando como máximo la mitad de los puntos podemos suponer que el segmento(a,b) es una arista del casco convexo de P. Una vez que esto es cierto, Q tiene la propiedad deseada si y sólo si el ordenamiento radial de Q alrededor del punto a es el mismo (o el inverso) que el ordenamiento radial alrededor del punto b. Por lo tanto, el resultado se sigue inmediatamente del teorema de Erdős-Szekeres. El caso en el que los dos órdenes ordenados son iguales es aquel en el que ninguna línea pasa por el segmento; el caso en el que el orden se invierte es aquel en el que todas las líneas pasan por el segmento.

Answer 3

Tengo mucha curiosidad por saber de dónde viene este problema, ya que está relacionado con algunas cosas que he estado pensando.

El contraejemplo más pequeño para k=1 parece ser el conjunto de seis puntos que contienen los vértices de un pentágono regular más su centro. Por desgracia, no sé cómo decir nada sobre este problema para k > 1.

Answer 4

Todavía no es una respuesta, pero me gusta esta pregunta y pensé en decir algo más:

Escriba N para |P| y considere m(P), el mínimo, sobre todo {a,b} en P, del número de líneas que unen dos elementos de P y que cruzan el segmento ab. Creo que lo que quieres es equivalente a un límite superior de este mínimo. (Los ejemplos de Reid muestran que no tiene por qué ser 0, en cualquier caso.) Estás preguntando si m(P) < cN para algún c < 1; me pregunto si no podría ser realmente o(N).

Traté de imaginar cómo resolvería este problema si fuera bueno en el análisis armónico y este es el pensamiento que tuve. Si m(P) es grande, entonces un montón de líneas que pasan por pares de puntos en P "casi se cruzan" donde cruzan un segmento de línea corto {a,b}. Así que la unión de todas estas líneas tiene más "focos" de los que cabría esperar. Encoge P para que quepa en un disco unitario. Sea delta algún número real pequeño que se optimizará más tarde. Para cada par x,y de P, dejemos que f_{x,y}, una función sobre el disco, sea la función característica del conjunto de puntos que están dentro de delta de la línea xy pero no dentro de delta de x o y -- un "rectángulo delgado dos veces perforado". Entonces sea f la suma de f(x,y) sobre todos los pares x e y.

Pensaría que si m(P) es grande, entonces f sería sorprendentemente grande en la vecindad de cualquier segmento de línea corto en P. Y supongo que la esperanza sería que se pudiera acotar |f|_p arriba de alguna otra manera para derivar una contradicción.

Actualización: Lo anterior ahora me parece un poco BSy, si alguien todavía está leyendo esto. En particular, me parece que o(N) es demasiado pedir. Me gustaría saber cuál es la respuesta para N = n^2 puntos de la red dispuestos en un cuadrado.

Answer 5

Una pregunta muy interesante. No tengo una respuesta, sólo una observación de que la propiedad que le pides a Q sólo depende del llamado "tipo de orden" de Q, un invariante combinatorio que lleva la cuenta de qué triples de puntos {a,b,c} en Q tienen la propiedad de que c está a la izquierda de la línea dirigida de a a b. El número de tipos de orden en un conjunto de tamaño n es del orden (n!)^4, como se ha comentado aquí en mi blog (en los comentarios.) Me pregunto cuántos de ellos contienen un par de puntos que se encuentran en el mismo lado de la línea que pasa por otros dos puntos.