¿Cuál es la probabilidad de cruzar dos segmentos de línea?

Question

Considere un espacio cuadrado.

Selecciona al azar 4 puntos.

Conecte aleatoriamente dos juegos de dos entre sí con segmentos de línea.

---

¿Cuál es la probabilidad de intersección de los segmentos de línea?

(Tal vez trataré de resolver esto con una pequeña simulación de Monte Carlo, pero estaría muy interesado en una solución analítica).

Answer 1

Vamos a ser muy claros acerca de los supuestos. Supongo que la "selección aleatoria de 4 puntos" a,B,C,D en la unidad de cuadrado significa seleccionar de manera uniforme y de forma independiente al azar sus coordenadas $x_A,y_A,x_B...$ $[0,1]$ rango; y que uno de los 6 posibles vinculaciones entre los puntos para formar los segmentos también es elegido de manera uniforme y de forma independiente al azar, para que el problema es equivalente a preguntar ¿cuál es la probabilidad de que, por ejemplo, AC y BD se cruzan.

---

Es fácil ver que la solución es $\frac{25}{108}$, o alrededor de $23\%$, si uno está dispuesto a tomar como dada la solución para Sylvester del cuatro-punto problema para la plaza-la probabilidad de que el casco convexo de cuatro puntos elegidos de manera uniforme y de forma independiente al azar en un cuadrado es un cuadrilátero, que es $\frac{25}{36}$. Es inmediato ver que dos segmentos elegidos por un sistema de emparejamiento al azar de cuatro puntos se cruzan si, y sólo si, el casco convexo de los cuatro puntos es de hecho un cuadrilátero, y los dos segmentos son sus diagonales. Si la primera condición es satisfecha, el último ocurre con una probabilidad de $\frac{1}{3}$ (la probabilidad de que un punto dado es emparejado con el "medio" de los tres restantes), produciendo una solución de $\frac{25}{36}\cdot\frac{1}{3}=\frac{25}{108}$ para el problema original.

---

Sylvester del cuatro-punto de problemas permite obtener la respuesta en exactamente la misma manera, incluso si los puntos son elegidos de manera uniforme al azar en otra convexa de la región, simplemente por la multiplicación por $\frac{1}{3}$. La fórmula general para Sylvester del cuatro-punto problema en una región convexa $R$, como se indica en el enlace de arriba, es igual a $1-4\frac{\bar{A_R}}{A(R)}$ donde $A(R)$ es el área de la región (en el caso de la unidad de la plaza, $1$) y $\bar{A}_R$ equivale a la espera que el área de un triángulo obtenido a partir de $3$ puntos elegidos uniformemente al azar dentro de ella. La fórmula se obtiene fácilmente observando que la probabilidad de que un determinado punto se encuentra en el triángulo formado por el otro$3$$\frac{\bar{A_R}}{A(R)}$, y desde los acontecimientos del este pasando por diferentes puntos son mutuamente excluyentes, la probabilidad de que ningún punto se encuentra en el triángulo formado por los otros tres es, de hecho,$1-4\frac{\bar{A}_R}{A(R)}$.

Computación $\frac{\bar{A_R}}{A(R)}$ no es trivial, en general. Si R es un cuadrado (en nuestro caso), una simple prueba de que $\frac{\bar{A_R}}{A(R)}=\frac{11}{144}$ puede ser encontrado aquí. Más en general, si R es el polígono regular de $n$ lados la solución está dada por Alikosky la fórmula, $\frac{\bar{A_R}}{A(R)}=\frac{9\cos^2 (2\pi/n)+52\cos(2\pi/n)+44}{36n^2\sin^2(2\pi/n)}$. Tenga en cuenta que esta es estrictamente una función decreciente de $n$, por lo que la intersección de probabilidad es estrictamente creciente con $n$, y el límite para $n\to\infty$, es decir,$\frac{35}{48\pi^2}$, los rendimientos de la solución a la hora de recoger los puntos en el círculo.

Así que, en general, la probabilidad de la intersección de $2$ segmentos, cada uno compuesto por $2$ puntos elegidos de manera uniforme y de forma independiente al azar de una regular $n$-agon o de cualquiera de sus transformaciones afines (tales como un rectángulo o un paralelogramo) es:

$\frac{1}{3}\left(1-4\cdot\frac{9\cos^2(2\pi/n) + 52\cos(2\pi/n) + 44}{36 n^2\sin^2 (2\pi/n)}\right)$

con el límite de $n\to\infty$, es decir,$\frac{1}{3}-\frac{35}{36\pi^2}$, lo que da la probabilidad de que al elegir los puntos de un círculo (o cualquier transformación afín, como una elipse).

Answer 2

Primero vamos a seleccionar 4 puntos dentro de un cuadrado. Deje $P_c$ ser una probabilidad de que estos 4 puntos forman una figura convexa (ninguno de los puntos seleccionados está dentro del triángulo formado por los otros tres).

Si este es el caso, la probabilidad de que dos segmentos de línea que se cruzan es 1/3.

De lo contrario, la probabilidad es 0.

Así, la probabilidad de que estamos buscando es:

$P=1/3 * P_c$

Ahora tenemos que encontrar el $P_c$.

Vamos a calcular la probabilidad de $P_1$ que el primer punto dentro del triángulo formado por los otros tres. Es $P_1 = S_{234}/S_{square}$ donde $S_{234}$ que se espera que el área del triángulo formado por los puntos 2, 3 y 4.

Mismo para $P_2$, $P_3$ y $P_4$. Obviamente $P_1=P_2=P_3=P_4$.

Probabilidad de que un punto está en el interior del triángulo formado por los otros 3 es $P_1+P_2+P_3+P_4$ porque no hay más de 1 de estos resultados puede ocurrieron al mismo tiempo.

$P_c = 1 - 4*P_1 = 1 - 4 * S_{234}$

Y ahora sólo tenemos que encontrar la $S_{234}$ - se espera que el área de un triángulo formado por seleccionados al azar 3 puntos dentro de un cuadrado.

El espera que el área de un triángulo formado por tres puntos elegidos al azar de la unidad de la plaza

Dicen que es $11/144$.

$P=1/3 * (1 - 4*11/144) = 25/108$

Este es un buen acuerdo con mis experimentos.

Answer 3

Si en cuatro puntos si$$\color{red}{1]}$ $ todos son colineales, los segmentos de línea nunca 'intersectarán'$$\color{red}{2]}$ $ Tres son colineales, aún no hay intersección. $$\color{red}{3]}$ $ Dos puntos siempre son colineales :)$$$ $$$..................................$$$$ $$ 4 puntos no colineales formarán cuadrilátero.

$$\color{red}{\text{if quadrilateral is convex}}$ $ Líneas segmentos dibujados deben ser lados o diagonales.

Sólo se cruzan las diagonales.$$$ $$$\color{red}{\text{if quadrilateral is concave}}$ $ Ninguna intersección

Resolver con esta información

Answer 4

Este es mi planteamiento:

Considere la posibilidad de una línea de $y=mx+c$ que se divide la unidad cuadrados en dos trapeziums. Que nos llame a la izquierda trapecio $a$, y el derecho trapecio $b$.

Mediante la resolución de las ecuaciones $(y=mx+c)=1$ $(y=mx+c)=0$ o$mx+c=1$$mx+c=0$, $x$- valores de las intersecciones de la se $x = \frac{-c+1}{m}$, e $\frac{-c}{m}$. Puesto que el $y$-valores de $0$$1$, la intersección de las coordenadas se $(\frac{-c}{m}, 0)$$(\frac{-c+1}{m}, 1)$.

Usando esta información, el área de un trapecio $a$ $1 * \frac{(-c/m+1)+(-c/m)}{2}$ $b$ $1 - (1 * \frac{(-c/m+1)+(-c/m)}{2})$ (desde $a+b=1$). La simplificación da a la zona de $a$$-\frac{c}{m}+ \frac{1}{2}$, y el área de $b$$\frac{c}{m}+\frac{1}{2}$.

Para la línea que conecta dos puntos para no cruzar la línea verde, los puntos no se en $a$$b$. Ya que el uso de la probabilidad geométrica, la probabilidad de que este es $ab-ba$, podemos restar esta condición de $1$ conseguir $1 - 2(-\frac{c}{m}+ \frac{1}{2})(\frac{c}{m}+\frac{1}{2})$, y después de la simplificación tenemos la probabilidad como $1 - 2(-\frac{c^2}{m^2}+\frac{1}{4})$ o $$\frac{2c^2}{m^2}+\frac{1}{2},$$

donde $c$ $y$intercepto de la línea (cuando extendida), y $m$ es su pendiente.

Nota: Este ejemplo no funciona al $c=0$, porque independientemente de lo $m$ es elegido, que sería igual a $0+\frac{1}{2}=\frac{1}{2}$, y cuando la línea se cruza un punto en el que no entre a $0$ $1$ al $x=0$ o $x=1$.