2
$\begingroup$

A square is bounded by the coordinates (0,0), (0,1), (1,0) and (1,1). Random x and y coordinates are chosen in the interval [0,1] for each of the n points. The n points are then randomly connected to form a cycle. What is the median area of this polygon?

$\endgroup$
3
  • 7
    $\begingroup$ Since by randomly connecting the n points you can get self-intersecting polygons, it seems most natural to consider the oriented area. In that case the median should be zero due to symmetry between clockwise and counter-clockwise orientations. $\endgroup$
    – j.c.
    Sep 19, 2013 at 23:03
  • 2
    $\begingroup$ Alternately one could take the convex hull of the $n$ points. $\endgroup$
    – Will Sawin
    Sep 20, 2013 at 0:29
  • 3
    $\begingroup$ See "Area Enclosed by the Convex Hull of a Set of Random Points" for Will's interpretation. There is a formula for the expected value. For three points, that value is $11/144$. $\endgroup$ Sep 20, 2013 at 1:20

1 Answer 1

6
$\begingroup$

Here is a technique which produces not just the median but the distribution of the area for $n=3$ in the square. See also Johan Philip, "The area of a random triangle in a square", but it seems this method is simpler.

Consider the bounding rectangle with sides parallel to the axes. (Philip used the bounding square with center $(1/2,1/2)$.) The area of the triangle is the product of $3$ independent random variables: The height of the bounding rectangle, the width of the bounding rectangle, and the proportion $P$ of the bounding rectangle taken up by the triangle.

The sides are distributed as the difference between the first and third order statistics of 3 IID uniform random variables, so the pdfs for the sides are $6x(1-x)$. Given the bounding rectangle, there are $2$ cases which occur with probabilities greater than $0$. Case 1: Two of the points are opposite vertices of the rectangle. Case 2: One point is a vertex (say, the bottom left) and the other two points are in the two sides not containing the vertex (the top side and the right side). The distribution of areas is a mixture over the distributions for these cases. One point has the middle $x$-value, and one point has the middle $y$-value. If these coincide, then two points are opposite vertices of the bounding rectangle, so case 1 occurs with probability $1/3$, and case 2 occurs with probability $2/3$.

If we rescale the bounding rectangle to the unit square, we can parametrize the cases by two coordinates. In the first case, the points are $(0,0), (1,1),$ and $(x,y)$ and the area of the triangle is $A_1(x,y)=|y-x|/2$. In the second case, without loss of generality the points are $(0,0), (x,1), (1,y)$ and the triangle has area $A_2(x,y)=1-x/2-y/2-(1-x)(1-y)/2 = 1/2 - xy/2$.

The probability density function for the proportion of the bounding rectangle filled by the triangle, conditioned on case $i$, is

$$\mu_i(z) = \int_{x=0}^{x=1} \sum_{y:A_i(x,y)=z} \bigg|\frac{\partial}{\partial y} A_i(x,y)\bigg|^{-1}dx.$$

$$\mu_1(z) = 2 \int_{x=2z}^{x=1} 2dx = 4(1-2z), z\in[0,1/2] $$

$$\mu_2(z) = \int_{x=1-2z}^{x=1} \frac{2}{x}dx=-2\log(1-2z), z\in[0,1/2]$$

$$\mu_P(z) = \frac{1}{3}\mu_1(z) + \frac{2}{3}\mu_2(z) = \frac{4}{3}(1-2z)-\frac{4}{3}\log(1-2z), z\in [0,1/2] $$

Now we have to multiplicatively convolve that with the distribution for the independent height and width of the bounding rectangle.

The dimensions of the bounding rectangle have probability density function $6z(1-z)$ for $z\in[0,1]$. The area of the bounding rectangle has probability density function (for $z\in[0,1]$)

$$\begin{eqnarray}\mu_R(z) &=& \int_{x=z}^{x=1} \mu_H(x) \mu_W(z/x) \bigg|\frac{\partial}{\partial y} xy |_{y=z/x} \bigg|^{-1} dx \newline &=& \int_{x=z}^{x=1} 6x(1-x) 6(z/x)(1-z/x) \frac{1}{x} dx \newline &=& -72z +72z^2 -36z\log z - 36z^2 \log z.\end{eqnarray}$$

To get the distribution for the area of a random triangle, we take the multiplicative convolution of the distribution of the area of the bounding rectangle and the distribution of the proportion of the bounding rectangle contained in the triangle.

$$\begin{eqnarray} \mu_A(z) &=& \int_{x=2z}^{x=1}\mu_R(x)\mu_P(z/x) \frac{1}{x} dx \newline &=& \int_{x=2z}^{x=1} \bigg(-72+72x-36\log x -36 x\log x\bigg)\bigg(\frac{4}{3}(1-\frac{2z}{x}) - \frac{4}{3} \log (1-\frac{2z}{x})\bigg)dx\end{eqnarray}$$

This integral is not elementary because of the $\int \log x \log(1-2z/x) dx$ and $\int x\log x \log(1-2z/x) dx$ terms which Mathematica evaluates in terms of $\operatorname{PolyLog}[2,x/(2z)].$ Other than those dilogarithms, though, the integral is elementary. For $z \in [0,1/2]$,

$$\begin{eqnarray}\mu_A(z) &=& 12 - (24 +16 \pi^2) z - (16 \pi^2 + 240 \log 2 - 48 (\log 2)^2)z^2 \newline & &- (12 + 96 z -240z^2)\log(1 - 2 z) +(48 \log 4 - 240) z^2 \log z + \newline & & 48 z^2 (\log z)^2 + (96 z+96z^2) \operatorname{PolyLog}[2, 2 z]. \end{eqnarray}$$

From this, the median $m$ can be expressed as the solution of $\int_{z=0}^{z=m} \mu_A(z) dz = 1/2$, which can be solved numerically, say by using Newton's method. Mathematics finds the numerical value of the median as $0.0571563.$ Not surprisingly, this is lower than the mean Joseph O'Rourke mentioned of $11/144 = 0.0763889$ (see Sylvester's problem for the square).

$\endgroup$
2
  • $\begingroup$ Thanks for the response. I don't quite understand the multiplicative convolution part. More specifically, I don't understand why the equation beginning with µ2(z) is true. Can someone explain or link me to an explanation? $\endgroup$
    – William
    Sep 23, 2013 at 22:38
  • $\begingroup$ @William: $\mu_2$ is the probability density function for the proportion of the rectangle covered by the triangle in case 2, or the probability density of $1/2(1-xy)$ where $x$ and $y$ are IID uniform on $[0,1]$. You can compute this by the formula I gave for $\mu_i$ above. For $1-2z \lt x \lt 1$ there is a unique solution $y\in[0,1], 1/2(1-xy)=z$. Compute $|\frac{\partial}{\partial y} 1/2(1-xy) |^{-1}$ at this point, $2/x$, and integrate this to get the uniform density on the square pushed forward to $[0,1/2]$ by $1/2(1-xy)$. $\endgroup$ Sep 24, 2013 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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