Estimación del número de puntos del casco convexo restringido en un triángulo

Question

Distribuyo los puntos uniformemente dentro de un triángulo equilátero:

Me gustaría hacer una estimación, para cualquier número de puntos distribuidos, de cuántos de esos puntos en promedio estarán en el casco convexo (puntos delineados en verde en el diagrama).

Espero evitar escribir un programa para trazar y medir empíricamente el número medio de puntos en el casco convexo para cada número de puntos distribuidos - ¿tal vez alguien ha propuesto ya un método general para estimar este valor?

Answer 1

Para el triángulo, $E_n = 2H_{n-1}$ donde $H_{n-1} = \sum\limits_{k=1}^{n-1} \frac{1}{k}$ es el $(n-1)^{th}$ Número armónico .

En general, si se toma una muestra $n$ puntos $x_1, \ldots, x_n$ uniformemente de un cuerpo convexo $K$ de la unidad de superficie y mira su casco convexo $C_n = \mathrm{co}(x_1,\ldots,x_n)$ . Tenemos la relación

$$\Delta_{n-1} = 1 - \frac{E_n}{n}$$

donde $E_n$ es el número esperado de vértices para $C_n$ y $\Delta_{n-1}$ es el área esperada de $C_{n-1} = \mathrm{co}(x_1,\ldots,x_{n-1})$ .

Podemos entender esta relación así. $E_n$ es $n$ veces la probabilidad de que $x_n$ es un vértice de $C_n$ . Dado que la probabilidad de que $x_n$ se encuentra en el borde de $C_{n-1}$ es cero, la probabilidad de que $x_n$ es un vértice de $C_n$ es la misma que la probabilidad de que $x_n \not\in C_{n-1}$ que a su vez es igual a $1 - \Delta_{n-1}$ .

Cuando $K$ es un triángulo, según este artículo en mathworld,

$$\Delta_n = 1 - \frac{2H_{n}}{n+1}$$

Esto significa que el número esperado de vértices que se busca es $E_n = 2 H_{n-1}$ .

Actualización

Para completar y documentar, permítanme explicar cómo calcular $\Delta_n$ y por lo tanto $E_n$ nosotros mismos.

Definir $\rho$ tal que $\frac{1}{\rho^2} = \frac{\sqrt{3}}{4}$ el área de un triángulo equilátero de lado $1$ . Tomaremos $K$ para ser el triángulo equilátero con vértices en $(0,0)$ y $(\rho\cos\frac{\pi}{6},\pm \rho\sin\frac{\pi}{6})$ .

Para cualquier $\theta \in [0,2\pi]$ y $p \in \mathbb{R}$ , dejemos que

• $\ell(\theta,p)$ sea la línea $\{ (x,y) : \cos\theta x + \sin\theta y = p \}$ .
• $L(\theta,p)$ sea la longitud del segmento de línea $\ell(\theta,p) \cap K$ .
• $H(\theta,p)$ sea el semiespacio $\{ (x,y) : \cos\theta x + \sin\theta y \le p \}$ .
• $A(\theta,p)$ sea el área de $H(\theta,p) \cap K$ .

Para cualquier $\lambda \in [0,1]$ , elija un $p$ para que $A(\theta,p) = \lambda$ . Sea $m(\theta,\lambda) = L(\theta,p)^2$ para este particular $p$ .

La repetición de argumentos en este respuesta y utilizando la simetría, $\Delta_n$ tiene la siguiente representación integral:

$$ \Delta_n = 1 - \frac{n}{6}\int_0^{2\pi} \int_0^1 \lambda^{n-1} m(\lambda,\theta) d\lambda = 1 - n \int_0^{\pi/3} \int_0^1 \lambda^{n-1} m(\lambda,\theta) d\lambda $$

Para cualquier $\lambda \in [0,\frac{\pi}{3}]$ , dejemos que $\tau = \frac{ \cos\left(\theta + \frac{\pi}{6}\right)}{ \cos\left(\theta - \frac{\pi}{6}\right)} $ se puede comprobar que $$m(\lambda,\theta ) = \frac{4}{\rho^2\cos^2\left(\theta-\frac{\pi}{6}\right)} \times \begin{cases} \frac{\lambda}{\tau},& \lambda \in [0,\tau]\\ \frac{1-\lambda}{1-\tau},& \lambda \in [\tau, 1 ] \end{cases} \quad\text{ and }\quad \frac{4 d\theta}{\rho^2\cos^2\left(\theta-\frac{\pi}{6}\right)} = 2d\tau $$

Integrar la primera pasada $\lambda$ y luego sobre $\tau$ obtenemos: $$\Delta_n = 1 - 2n\int_0^1 \int_0^1 \lambda^{n-1} m(\lambda,\theta) d\lambda d\tau = 1 - \frac{2}{n+1}\int_0^1 \frac{1-\tau^n}{1-\tau} d\tau = 1 - \frac{2H_n}{n+1}$$