22 votos

Puntos y líneas en el plano

Hace un número real positivo de $k\geq1$ existe tal que para todo conjunto finito de $P$ de puntos en el plano (con la propiedad de que no hay tres puntos de $P$ mentir en una línea común y $|P|\geq3$), uno puede elegir un subconjunto de $P$ de $P$ con $|Q| \geq |P|/k$ puntos y con la propiedad de que existen dos diferentes puntos de $a$ y $b$ en $Q$ que no hay una línea de $\overline{(p,q)}$ a través de dos diferentes puntos $p,q$ de $Q\ \ barra invertida\{a,b\}$ cruza el interior del segmento $(a,b)$?

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

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

124voto

RodeoClown Puntos 3949

Yo apuesto a que la respuesta a esta pregunta es que tal k no existe. Con el fin de construir un contrexample para cualquier k yo consideraría un gran cuadrado de la talla Nk x Nk, N>>1 y tomar todos los enteros puntos dentro de ella. Ahora perturbar sólo un poco poco todos estos (Nk)^2 puntos de tal manera, que no 3 laicos en una línea. Se ve que esta configuración será contrexample para la gran N. La razón para pensar de este modo es que antes de perterb este configuartion para cada segmento ab hay aproximadamente al menos aproximadamente (Nk)^3 pares de puntos en el interior de la plaza tal que la línea de tiro de ellos se cruzan segmento dado. Parece que usted tiene que lanzar demasiados puntos.

11voto

Flow Puntos 14132

No es lo mismo, pero por cada dos puntos a y b en P, existe un subconjunto P de P con |Q| = Ω(√|P|) por lo que no hay una línea de(p,q) a través de dos puntos de Q cruza segmento(a,b), o de cada línea(p,q), se cruza el segmento.

Para ver esto, observe primero que mediante la eliminación de la mitad de los puntos que podemos asumir que el segmento(a,b) es un borde del casco convexo de P. una Vez que esto es cierto, Q tiene la propiedad deseada si y sólo si la radial ordenada de P alrededor del punto a es el mismo (o a la inversa) de) la radial se ordena alrededor del punto b. Por lo tanto, el resultado se sigue inmediatamente de la Erdős–Szekeres teorema. En el caso de que los dos se ordenan los pedidos son de la misma es en el que no hay ninguna línea que pasa por el segmento; el caso en que el orden se invierte es en el que cada línea que pasa por el segmento.

9voto

csmba Puntos 2440

Soy muy curioso este problema procede, puesto 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 contiene los vértices de un Pentágono regular y su centro. Por desgracia, no sé decir nada acerca de este problema para k > 1.

3voto

Todavía no es una respuesta, pero me gusta esta pregunta y pensé que diría un poco más:

Escriba N para |P| y considerar la posibilidad de m(P), el infimum, sobre todo {a,b} en P, el número de líneas que se unen dos elementos de P y que se cruzan con el segmento ab. Creo que lo que quiere es equivalente a un límite superior en este infimum. (Reid ejemplos se muestra que no tiene que ser 0, en cualquier caso.) Usted está preguntando si m(P) < cN para algunos c < 1; me pregunto si en realidad no podría ser o(N).

Traté de imaginar cómo iba a resolver este problema si yo fuera bueno en análisis armónico y este es el pensamiento que tenía. Si m(P) es grande, entonces un montón de líneas a través de pares de puntos en P "casi se cruzan", donde se cruzan un pequeño segmento de la línea de {a,b}. Así que la unión de todas estas líneas tienen más "se centra" que se podría esperar. Reducir P para que quepa en una unidad de disco. Vamos a delta ser algún pequeño número real para ser optimizado más tarde. Para cada par x,y de P, vamos a f_{x,y}, una función en el disco, de ser la función característica del conjunto de puntos que están dentro de la delta de la línea xy, pero no dentro de la delta de x o de y, un "doble-perforado fino rectángulo". Entonces sea f la suma de f(x,y) sobre todos los pares de x y y.

Yo pienso que si m(P) es grande, entonces f sería sorprendentemente grande en la vecindad de cualquier segmento de línea en P. Y supongo que la esperanza que usted podría obligado |f|_p antes, en algunos otros, así como para derivar una contradicción.

Actualización: El de arriba ahora parece clase de BSy a mí, si alguien sigue leyendo esto. En particular, creo que o(N) parece demasiado pedir. Me gustaría saber cuál es la respuesta para N = n^2 entramado de puntos dispuestos en un cuadrado.

1voto

Pregunta muy interesante. No tengo una respuesta, sólo un comentario de que la propiedad que usted pregunte Q tener sólo depende de la denominada "tipo de pedido" de Q, una combinatoria invariantes que sigue la pista de que tripletas de puntos {a,b,c} en P tienen la propiedad de que c está a la izquierda de la orientación de la línea de a a b. El número de tipos de orden en un conjunto de tamaño n es el orden (n!)^4, como se discute aquí en mi blog (en los comentarios.) Me pregunto cuántos de estos contienen un par de puntos que se encuentran en el mismo lado de la línea a través de cualquiera de los otros dos puntos?

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