3
$\begingroup$

I am distributing points uniformly within an equilateral triangle:

I would like to make a guess, for any given number of distributed points, how many of those points on average will be on the convex hull (points outlined green on the diagram).

I'm hoping to avoid writing a program to empirically plot and measure the mean number of points on the convex hull for each number of distributed points - perhaps someone has already proposed a general method for estimating this value?

$\endgroup$
  • 2
    $\begingroup$ Preparata & Shamos report the pretty precise result from link.springer.com/article/10.1007%2FBF00535300?LI=true $E(h)=2r/3(\gamma+\ln N)+O(1)$ for a convex $r$-gon. $\endgroup$ – Yves Daoust Nov 22 '16 at 20:09
  • $\begingroup$ Where $\gamma$ is Euler's constant, I suppose. Very interesting. $\endgroup$ – Jean Marie Nov 22 '16 at 20:11
  • $\begingroup$ Yep, that's it . $\endgroup$ – Yves Daoust Nov 22 '16 at 20:12
2
$\begingroup$

For triangle, $E_n = 2H_{n-1}$ where $H_{n-1} = \sum\limits_{k=1}^{n-1} \frac{1}{k}$ is the $(n-1)^{th}$ Harmonic number.

In general, if you sample $n$ points $x_1, \ldots, x_n$ uniformly from a convex body $K$ of unit area and look at their convex hull $C_n = \mathrm{co}(x_1,\ldots,x_n)$. We have the relation

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

where $E_n$ is the expected number of vertices for $C_n$ and $\Delta_{n-1}$ is the expected area of $C_{n-1} = \mathrm{co}(x_1,\ldots,x_{n-1})$.

We can understand this relation like this. $E_n$ is $n$ times the probability that $x_n$ is a vertex of $C_n$. Since the probability that $x_n$ lies on the edge of $C_{n-1}$ is zero, the probability that $x_n$ is a vertex of $C_n$ is the same as the probability that $x_n \not\in C_{n-1}$ which in turn equals to $1 - \Delta_{n-1}$.

When $K$ is a triangle, according to this article on mathworld,

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

This means the expected number of vertices you seek is $E_n = 2 H_{n-1}$.

Update

For completeness and documentation purposes, let me outline how to compute $\Delta_n$ and hence $E_n$ ourselves.

Define $\rho$ such that $\frac{1}{\rho^2} = \frac{\sqrt{3}}{4}$, the area of an equilateral triangle of side length $1$. We will take $K$ to be the equilateral triangle with vertices at $(0,0)$ and $(\rho\cos\frac{\pi}{6},\pm \rho\sin\frac{\pi}{6})$.

For any $\theta \in [0,2\pi]$ and $p \in \mathbb{R}$, let

  • $\ell(\theta,p)$ be the line $\{ (x,y) : \cos\theta x + \sin\theta y = p \}$.
  • $L(\theta,p)$ be the length of the line segment $\ell(\theta,p) \cap K$.
  • $H(\theta,p)$ be the half-space $\{ (x,y) : \cos\theta x + \sin\theta y \le p \}$.
  • $A(\theta,p)$ be the area of $H(\theta,p) \cap K$.

For any $\lambda \in [0,1]$, choose a $p$ so that $A(\theta,p) = \lambda$. Let $m(\theta,\lambda) = L(\theta,p)^2$ for this particular $p$.

Repeating arguments in this answer and using symmetry, $\Delta_n$ has following integral representation:

$$ \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 $$

For any $\lambda \in [0,\frac{\pi}{3}]$, let $\tau = \frac{ \cos\left(\theta + \frac{\pi}{6}\right)}{ \cos\left(\theta - \frac{\pi}{6}\right)} $, one can check that $$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 $$

Integrate first over $\lambda$ and then over $\tau$, we obtain: $$\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}$$

$\endgroup$
  • 1
    $\begingroup$ There's a mistake in the definition of $H_n$ in the first line. $\endgroup$ – Sophie Nov 24 '16 at 0:03
  • $\begingroup$ @Sophie fixed - thanks for catching that. $\endgroup$ – achille hui Nov 24 '16 at 3:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.