Random convex polygons I

As I mentioned in one of my earlier posts, the early work of Renyi and Sulanke on  random planar convex polygons was available only in German.    This consists of three separate articles published over a couple of years.     Now, courtesy of the efforts  of  Manfred Weis,   English   translations are available to  the non-German-reading audience. What follows is the first in this series of articles.

Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2 (1963) 75-84.


On the Convex Hull of $n$ Randomly Chosen Points I

by

A.Rényi and R. Sulanke



Introduction

Let $P_i (i=1,2,\cdots, n)$ be $n$ points of the plane chosen randomly according to a certain distribution and, let $H_n$ denote the convex hull of these points, which is a convex polygon as is commonly known. The number $X_n$ of sides of $H_n$ is then a random variable, whose behavior as $n\rightarrow\infty$ under various assumptions on the distribution of the points $P_i$ will be investigated in this paper. To this end It is assumed that the points $P_i$ are distributed independently and according to the same distribution. By $E_n=E(X_n)$ we denote the mathematical expected value of $X_n$. 

​ In § 1 we consider the case that the $P_i (i=1, \cdots,\ n)$ are distributed equally in a convex Polygon $K$ with $r$ corners. It will be shown that $E_n=(2r/3)(\log n+C)+T+\omicron(1)$; here $C$ denotes the Euler constant. The value $T=T(k)$ depends on the region $K$. In § 2 we prove the elementary geometric theorem that $T(k)$ will be maximal for polygons that are affinely equivalent to the regular $r$-gons and only for those.  In § 3 the asymptotic behavior of $E_n$ will be investigated if the $P_i$ are distributed in a convex region with smooth boundary. It turns out that $E_n$ has $\sqrt[3]{n}$ order of magnitude. In § 4 we finally prove that $E_n$ behaves as $\sqrt{\log n}$ if the points $P_i$ are normally distributed.

§1 . Random points in a convex polygon

​ Let $K$ be a convex polygon with corners $A_1,\ A_2,\ \dots,\ A_r$ and the corresponding angles $\vartheta_1,\ \vartheta_2,\ \dots,\ \vartheta_r$. Let $a_k$ denote the length of the side $A_kA_{k+1}$ ($k=1,\ \dots,\ r$; $A_{r+1}=A_1$). Let further $F$ denote the area of $K$.

​ Let $\varepsilon_{ij}=1$, if $i\ne j$ and the edge $P_iP_j$ is part of the boundary of $H_n$, and $\varepsilon_{ij}=0$ otherwise. Then obviously

$$(1) \quad X_n =\sum_{1\leqq i\lt j\leqq n}{\varepsilon_{ij}}$$

The probability

$$(2)\quad W_n=P(\varepsilon_{ij}=1)$$

is the same for pairs $(i,j)$ of numbers with $1\leqq i\lt j\leqq n$ and it holds true that

$$(3)\quad E_n = E(X_n)=\binom{n}{2}W_n$$

To determine the asymptotic behavior of $E_n$ it therefore suffices to calculate the probability $W_n$. Now $W_n$ is the probability  that all points $P_h$ ($h=3,\ 4,\ \dots,\ n$) lie to the same side of the line through $P_1$ and $P_2$. If we denote by $F_1\le F/2$ and $F-F_1$ the areas of the parts of $K$ in which $K$ is divided by the line $P_1P_2$, it holds true that

$$(4)\quad W_n=\frac{1}{F^2}\int_K\int_K\left[\left(1-\frac{F_1}{F}\right)^{n-2}+\left(\frac{F_1}{F}\right)^{n-2}\right]dP_1dP_2$$

Obviously, because $F_1/F\le1/2$,

$$\frac{1}{F^2}\int_K\int_K\left(\frac{F_1}{F}\right)dP_1dP_2\leqq\frac{1}{2^{n-2}}$$

and therefore

$$(5)\quad E_n\sim\frac{\binom{n}{2}}{F^2} \int_K\int_K\left(1-\frac{F_1}{F}\right)^{n-2}dP_1dP_2,$$

where $\sim$ means "asymptotically equal", i.e.,  $A_n\sim B_n$ means that $\lim_{n\rightarrow+\infty}\frac{A_n}{B_n}=1$.

​ Let now $f_i$ denote the area of the triangle $A_{i-1}A_iA_{i+1}$ ($A_{r+j}=A_j$), and be $f=\min_{1\leqq i\leqq r}{f_i}$. Obviously we can restrict ourselves to such point pairs $P_1$, $P_2$ for which the line $P_1P_2$ either hits two neighboring sides or two sides that are separated by another side of $K$. This is so because for all other lines $1-F_1/F\leqq1-f/F$. Therefore we can neglect the right side of $(5)$ and it holds true that

$$(6)\quad E_n\sim\frac{\binom{n}{2}}{F^2}\left(\sum_{i=1}^r\left(i+J_i\right)\right),$$

where

$$(7)\quad I_i =\int_{C_i}\left(1-\frac{F_1}{F}\right)^{n-2}dP_1dP_2$$

and

$$(8)\quad I_i =\int_{D_i}\left(1-\frac{F_1}{F}\right)^{n-2}dP_1dP_2$$

Here $C_i$ denotes the set of point pairs $P_1$, $P_2$ for which the line $P_1P_2$ hits the sides $A_{i-1}A_i$ and $A_iA_{i+1}$ of $K$, and $D_i$ the set of point pairs for which the line $P_1P_2$ hits the sides $A_{i-1}A_i$ and $A_{i+1}A_{i+2}$ of $K$.

​ We first investigate the integral $I_i$. Let $G_{ab}$ denote the set of point pairs $P_1$, $P_2$ for which the $|A_iQ_1|\lt a$ and $|A_iQ_2|\lt b$ holds; here $Q_1$ denotes the intersection point of line $P_1P_2$ with side $A_{i-1}A_i$ and $Q_2$ its intersection point with side $A_iA_{i+1}$, further $|AB\ |$ denotes the length of the segment $AB$.

Via an elementary calculation it turns out that

$$(9)\quad\int_{G_{ab}}dP_1dP_2 =\frac{a^2b^2\sin^2\vartheta_i}{12}$$

The area of the triangle $Q_1A_iQ_2$ that is cut off by the line $P_1P_2$ equals $1/2\ a\,b\sin\vartheta_i$ . Therefore we  have

$$(10)\quad I_i=\int_0^{a_{i-1}}\int_0^{a_i}\left(1-\frac{a\,b\sin\vartheta_i}{2F}\right)^{n-2}\sin^2\vartheta_i\frac{a\,b}{3}\,da\, db,$$

where $a_i$ denotes the length of side $A_iA_{i+1}$.

Via the transformation

$$(11)\quad X= a\sqrt{\frac{\sin\vartheta_i}{2\,F}},\quad Y= b\sqrt{\frac{\sin\vartheta_i}{2\,F}}$$

we get

$$(12)\quad I_i =\frac{4\,F^2}{3}\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-2}XY\,dX\,dY,$$

where

$$\quad X_i=a_{i-1}\,\sqrt{\frac{\sin\vartheta_i}{2F}},\quad Y_i=a_i\,\sqrt{\frac{\sin\vartheta_i}{2F}},$$

therefore

$$(13)\quad\varrho_i = X_iY_i=\frac{a_{i-1}a_i\sin\vartheta_i}{2\,F}=\frac{f_i}{F}\lt 1$$

holds true. Now we have

$$\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-2}XY\,dX\,dY=\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-2}dX\,dY-\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-1}XY\,dX\,dY$$

Further it is true that

$$\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-1}XY\,dX\,dY=\int_0^{X_i}\frac{1-\left(1-XY_i\right)^n}{n}dX=$$

$$\quad =\frac{1+\frac{1}{2}+\cdots+\frac{1}{n}-\sum_{k=1}^n{\frac{\left(1-\varrho_i\right)^k}{k}}}{n}$$

thus we get

$$(14)\quad I_i=\frac{4\,F^2}{3}\left\lbrace\frac{\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}}{n(n-1)}-\frac{\sum_{k=1}^{n-1}\frac{(1-\varrho_i)^k}{k}}{n(n-1)}+\frac{(1-\varrho_i)^n}{n^2}\right\rbrace$$

If we set

$$(15)\quad S_i=\sum_{k=1}^\infty\frac{(1-\varrho_i)^k}{k}=\log\frac{1}{\varrho_i},$$

that finally results in

$$(16)\quad E_n=\frac{2}{3}\left(C-1+\log n\right)r-\frac{2}{3}\sum_{i=1}^rS_i+\omicron(1)+\frac{\binom{n}{2}}{F^2}\sum_{i=1}^rJ_i,$$

where $C$ is the Euler constant.

​ Now we calculate the integral $J_i$ .We extend the sides $A_{i-1}A_i$ and $A_{i+2}A_{i+2}$ to their intersection point $A_i^*$; the case that these sides are parallel can be treated similarly. Let again $Q_1$ be the intersection point of lines $P_1P_2$ with the side $A_{i-1}A_i$ and $Q_2$ be the intersection point with the side $A_{i+1}A_{i+2}$ and let $a' = |A_iA_i^*|$, $b'=|A_{i+1}A_i^*|$, $a=|A_iQ_1|$,  $b=|A_{i+1}Q_2|$; $G_{ab}$ be defined as above. We obtain from $(9)$

$$(17)\quad\int_{G_{ab}}dP_1\,dP_2=\frac{\sin^2\gamma_i}{12}\left(a^2+2aa'\right)\left(b^2+2bb'\right)$$

where $\gamma_i$ denotes the angle at $A_i^*$. Consequently

$$(18)\quad J_i=\int_{D_i}\left(1-\frac{(ab+a'b+ab')\sin\gamma_i}{2F}\right)^{n-2}\frac{\sin^2\gamma_i}{3}(a+a')(b+b')da\,db$$

and that integral is asymptotically equal to

$$(19)\quad J_i\sim \int_{D_i}\left(1-\frac{(a'b+ab')\sin\gamma_i}{2F}\right)^{n-2}\frac{\sin^2\gamma_i}{3}a'b'\,da\,db$$

If we carry out the transformation

$$ \quad a=\frac{F}{b'\sin\gamma_i},\quad b=\frac{F}{a'\sin\gamma_i}Y$$

it follows that

$$\quad J_i\sim\frac{F^2}{3}\int_0^{a'_{i-1}}\int_0^{a'_{i+1}}\left(1-\frac{X+Y}{2}\right)^{n-2}dX\,dY=$$

$$\quad=\frac{4\,F^2}{3n(n-1)}\left\lbrace1-\left(1-\frac{a'_{i-1}}{2}\right)^n-\left(1-\frac{a'_{i+1}}{2}\right)^n+\left(1-\frac{a'_{i-1}+a'_{i+1}}{2}\right)^n\right\rbrace,$$

where

$$\quad a'_{i-1} = \frac{a_ib'\sin\gamma_i}{F},\quad  a'_{i+1} = \frac{a_{i+2}a'\sin\gamma_i}{F}$$

has been set. Consequently this yields

$$\quad E_n=\frac{2r}{3}\left(\log n+C\right)-\frac{2}{3}\sum_{i=1}^rS_i+\omicron(1).$$

Lets summarize what  has been proven in the following theorem:

Theorem 1.  Let $K$ be  a convex polygon with $r$ sides. The mathematical expectation $E_n$ of the number of sides of the convex hull $H_n$ of $n$ in $K$ randomly chosen points is equal to

$$(20)\quad E_n=\frac{2r}{3}\left(\log n+C\right)+\frac{2}{3}\log\frac{\prod_1^rf_i}{F^r}+\omicron(1)$$

Here $F$ denotes the area of $K$ and $f_i$ the area of the triangle that is defined by corners $A_{i-1}A_iA_{i+1}$ of $K$.

​ If for example $K$ is a triangle, then $f_1=f_2=f_3=F$ and it follows that

$$(21)\quad E_n=2(\log n+C)+\omicron(1).$$

The formula for $E_n$ doesn't depend on the shape of the triangle. That is reasonable because $E_n$ must obviously be invariant under affine transformations. In §2 we will show the constant

$$(22)\quad Z(K)=\frac{\prod_1^rf_i}{F^r}$$

 that appears in $(20)$ and depends on the shape of $K$ becomes maximal for regular $r$-gons (and for the polygons that are affinely equivalent to them).



§ 2. An Extremal Value Problem for Convex Polygons

​ Before we turn to further asymptotic estimates for $E_n$ under different conditions on the distribution of the points $P_i$, we prove the following

​Theorem 2. Let $K$ be a convex polygon with $r$ sides. Then we have with notations of the previous §: The function

$$(23)\quad Z(K)=\frac{1}{F^r}\prod_{i=1}^{r}f_i$$

is maximal if and only if $K$ can be affinely transformed to the regular $r$-gon.

​ Let $\mathfrak{a}_i=\overrightarrow{A_{i-1}A_i}$, where $A_{r+i}=A_i$ shall be set. Then it holds true that

$$(24)\quad f_i=\frac{1}{2}[\mathfrak{a}_i,\mathfrak{a}_{i+1}],\quad F=\frac{1}{2}\sum_{i=1}^{r-2}[\mathfrak{a}_1+\mathfrak{a}_2+\cdots+\mathfrak{a}_i,\mathfrak{a}_{i+1}]$$

where $[\mathfrak{a},\mathfrak{b}]$ denotes the determinant of vectors  $\mathfrak{a},\mathfrak{b}$. The function $Z(K)$ is now a function of the $r$ vectors $\mathfrak{a}_i$ ($i=1,\,\dots,\,r$) , which satisfy the closing condition

$$(25)\quad\sum_{i=1}^r\mathfrak{a}_i=0$$

We now imagine the corners $A_i$ of $K$ subjected to sufficiently small displacements, that depend continuously differentiable on a parameter $t$. As the original polyon $K$ that shall correspond to parameter value $t=0$ is a convex $r$-gon, then also the polygons that are generated by sufficiently small displacements will be convex $r$-gons. The function $Z$ when considered as a function of $t$ must have a maximum at $T=0$ if $K$ is a maximal polygon. As a necessary condition for $K$ being maximal we get by elementary calculation:

$$(26)\quad\sum_{i=1}^r\frac{F}{f_i}\left(\left[\mathfrak{\dot a}_i+\mathfrak{a}_{i+1}\right]+\left[\mathfrak{a}_i+\mathfrak{\dot a}_{i+1}\right]\right )\ -$$

$$\quad\ -\ r\sum_{i=1}^{r-2}\left(\left[\mathfrak{\dot a}_1+\cdots+\mathfrak{\dot a}_i,\mathfrak{a}_{i+1}\right]+\left[\mathfrak{a}_1+\cdots+\mathfrak{ a}_i,\mathfrak{\dot a}_{i+1}\right]\right )=0$$

Here

$$\quad \mathfrak{\dot a}_i=\frac{d}{dt}\mathfrak{a}\Bigg|_{i=0}$$

has been set. The $\mathfrak{\dot a}$ are arbitrary vectors that only have to satisfy the closing conditions

$$(27)\quad\sum_{i=1}^r\mathfrak{\dot a}_i=0$$

that follow from $(25)$. If we now one by one set

$$(28)\quad \mathfrak{\dot a}_j=\mathfrak{b},\ \mathfrak{\dot a}_{j+1}=-\mathfrak{b},\ \mathfrak{\dot a}_i=0 \text{ for } i\ne j,\ j+1,$$

where $\mathfrak{b}$ presently still is an arbitrary vector, the closing condition is obviously fulfilled and for $j\,=\,1,\,  \ldots,\,r$  we obtain

$$(29)\quad\frac{F}{r}\left\lbrace\frac{[\mathfrak{a}_j,\mathfrak{b}]}{f_{j-1}}-\frac{[\mathfrak{b},\mathfrak{a}_{j+2}]}{f_{j+1}}+\frac{1}{f_j}[\mathfrak{b},\mathfrak{a}_j+\mathfrak{a}_{j+1}]\right\rbrace=[\mathfrak{b},\mathfrak{a}_j+\mathfrak{a}_{j+1}].$$

if we now set specifically $\mathfrak{b}=-\mathfrak{a}_j$, then consequently

$$(30)\quad\frac{F}{r}\left\lbrace4-\frac{[\mathfrak{a}_j,\mathfrak{a}_{j+2}]}{f_{j+1}}\right\rbrace=2f_j$$

and for setting $\mathfrak{b}=-\mathfrak{a}_{j+1}$ we get

$$(31)\quad\frac{F}{r}\left\lbrace4-\frac{[\mathfrak{a}_{j-1},\mathfrak{a}_{j+1}]}{f_{j-1}}\right\rbrace =2f_j$$

Comparing these formulas yields

$$(32)\quad[\mathfrak{a}_j,\mathfrak{a}_{j+2}]=\frac{f_{j+1}}{f_{j-1}}[\mathfrak{a}_{j-1},\mathfrak{a}_{j+1}]$$

We now write $(31)$ in the form

$$\quad 2\left(2-\frac{rf_j}{F}\right)=\frac{[\mathfrak{a}_{j-1},\mathfrak{a}_{j+1}]}{f_{j-1}}$$

and obtain by repeated application of $(32)​$

$$\quad\quad 2\left(2-\frac{rf_j}{F}\right)=\frac{f_j}{f_1\cdot f_2}[\mathfrak{a}_1,\mathfrak{a}_3]$$

or

$$(33)\quad f_j=\frac{2}{\frac{r}{F}+\frac{[\mathfrak{a}_1,\mathfrak{a}_3]}{2f_1\cdot f_2}}$$

For $r=3$ our optimization task is trivial. In case $r\geqq 4$ we first get $f_3=f_4=\cdots=f_r$. By a cyclic exchanging of the numbering of the corners of $K$ it immediately follows that

$$(34)\quad f_1=f_2=\cdots=f_r$$

and according to $(32)$ besides that we get

$$(35)\quad [\mathfrak{a}_i,\mathfrak{a}_{i+2}]= [\mathfrak{a}_1,\mathfrak{a}_3]=\mathfrak{b}\quad(i=1,2,\ldots,r)$$

where $b$ is a certain constant.

​Remark In case $b=[\mathfrak{a}_i,\mathfrak{a}_{i+2}]=0$ we have $f_j=2F/r$. Therefore $\mathfrak{a}_[i+2]$ is always parallel to $\mathfrak{a}_i$. That is only possible if $r=4$ and $K$ is a parallelogram.

​ We now return to the general case. Via an affine transformation we can always achieve that $f_i=1/2$, i.e. we have

$$(36)\quad[\mathfrak{a}_i,\mathfrak{a}_{i+1}]=1$$

Then from $(33)$ follows immediately

$$(37)\quad F=\frac{r}{2(2-b)} \text{ and therefore }b\lt2.$$

As the vectors $\mathfrak{a}_{i-2}$ and $\mathfrak{a}_{i-1}$ are linearly independent, the ansatz $\mathfrak{a}_i=\alpha\mathfrak{a}_{i-2}+\beta\mathfrak{a}_{i-1}$ and keeping in mind $(35)$ and $(36)$ leads to the recursion

$$(38)\quad\mathfrak{a}_i=-\mathfrak{a}_{i-2}+b\mathfrak{a}_{i-1}$$

We have consequently shown that the side's vectors $\mathfrak{a}_i$ of a maximal convex $r$-gon must necessarily satisfy a recursion of type $(38)$. The proof will now be carried to an end by showing that in that case an Euclidean metric can be defined in the affine plane that lets polygon $K$ appear to be a regular $r$-gon.

​ First we remark that always

$$(39)\quad-1\leqq b\le2$$

must be true. Were namely $b\lt -1$ then side $\mathfrak{a}_3$ would penetrate side $\mathfrak{a}_1$, which would contradict the convexity of $K$. The estimate $b\lt2$ for the upper bound has already been proven ($(37)$).

​ The Euclidean metric is uniquely determined if we fix the skalar products of the vectors $\mathfrak{a}_1$, $\mathfrak{a}_2$, which we consider to be basis vectors. We define these skalar products via

$$(40)\quad\mathfrak{a}_1^2=\mathfrak{a}_2^2=\frac{2}{\sqrt{4-b^2}},\quad\mathfrak{a}_1\mathfrak{a}_2=\frac{b}{4-b^2}$$

Obviously

$$\quad[\mathfrak{a}_1,\mathfrak{a}_2]^2=\begin{vmatrix}\mathfrak{a}_1^2&\mathfrak{a}_1\mathfrak{a}_2\\ \mathfrak{a}_1\mathfrak{a}_2&\mathfrak{a}_2^2\end{vmatrix}=1$$

Therefore the so defined metric is positiv definite, i.e. Euclidean. Via complete induction, utilizing $(38)$, it is easy to prove that for all $j$

$$\quad\mathfrak{a}_j^2=\frac{2}{\sqrt{4-b^2}},\quad \mathfrak{a}_j\mathfrak{a}_{j+1}=\frac{b}{\sqrt{4-b^2}},\quad[\mathfrak{a}_j,\mathfrak{a}_{j+1}]=1$$

must be true. From this it follows that all sides of our $r$-gon $K$ must have equal length and that two consecutive sides intersect under the same angle. Therefore that $r$-go must be regular with respect to that metric.

​ Thus the uniqueness of the maximal polygon has been proven. The existence is the result of an easy conclusion from the boundedness of $Z(K)$, as well as the continuity of $F$ and $Z$. Therefore theorem 2 is completely proven.



§ 3. Random points in a convex region with smooth boundary

​ Let $K$ now be a convex region whose boundary has a curvature that is a continuous function of arclength. With the notations of the previous paragraphs we again have

$$E_n=\binom{n}{2}W_n.$$

According to known theorem of integral geometry (cf. Blaschke[1], p17, (86)) the density for point-pairs can be reformulated as follows:
$$(41)\quad dP_1\,dP_2=|t_1-t_2|\,dt_1\,dt_2\,d\varphi\,dp,$$

with p meaning the distance of the line $P_1\,P_2$ from the coordinate origin and, $\varphi$ the angle with a zero-direction (translator's remark: that means "a reference direction" that corresponds to the angle of 0°)  and $t_1,$ $t_2$ the parameter values of the arc-length of points $P_1$, $P_2$ on the line $P_1\,P_2$. Let $f$ denote the area of the part of $K$ that is cut off by the line $P_1\,P_2$. Then we have

$$(42)\quad E_n=\frac{\binom{n}{2}}{F^2}\int_0^{2\pi}\left\lbrace\int_0^{p(\varphi)}\left(1-\frac{f}{F}\right)^{n-2}\left(\iint|t_1-t_2|\,dt_1\,dt_2\right)dp\right\rbrace d\varphi$$

By $l(p,\varphi)$ we denote the length of the chord in which the line with coordinates $p$, $\varphi$ hits region $K$. Then it holds true that

$$(43)\quad\iint\left|t_1-t_2\right|\,dt_1\,dt_2=\frac{l^3(p,\varphi)}{3}$$

From this we get

$$(44)\quad E_n=\frac{\binom{n}{2}}{3F^2}\int_0^{2\pi}\left\lbrace\left(1-\frac{f}{F}\right)^{n-3}l^3(p,\varphi)\,dp\right\rbrace\,d\varphi.$$

When calculating the asymptotic value of $E_n$ one can obviously restrict to pairs of values $p$, $f/F\lt \varepsilon$ because the other value-pair only contribute to an error term of magnitude $n^2(1-\varepsilon)^n=\omicron(1)$. We now consider a fixed value of $\varphi$. Let $P(\varphi)$  be the point in which the tangent of  $K$ has direction $\varphi$. In the calculation of $E_n$ one may replace $f$ and $l$ with the corresponding values$\bar f$ and $\bar l$ of the osculating circle in point $P(\varphi)$, as turns out from the following estimations. Let $\alpha$ be the central angle related to chord $\bar l$ and $r(\varphi)$ the radius of the osculating circle in point $P(\varphi)$. Then

$$(45)\quad\bar l = 2r(\varphi)\,sin\,\alpha/2\quad\text{and}\quad\bar f=\frac{1}{2}(\alpha-\sin\alpha)r^2(\varphi)$$

furthermore

$$(46)\quad\left|dp\right|=\frac{1}{2}r(\varphi)\sin\alpha/2\left|d\alpha\right|$$

and finally

$$(47)\quad l-\bar l=\omicron(\alpha^2)\quad\text{and}\quad f-\bar f=\omicron(\alpha^4)$$

From which we get

$$(48)\quad E_n=\frac{\binom{n}{2}}{12F^2}\int_0^{2\pi}r^4\int_0^{\alpha(\varphi)}\left(1-\frac{\alpha^3r^2}{12F^2}+\omicron(\alpha^3)\right)^{n-2}\left(\alpha^4+\omicron(\alpha^5)\right)\,d\alpha\,d\varphi$$.

By substituting

$$(49)\quad\frac{\alpha^3r^2}{12F}=\frac{X}{n}$$

we get

$$\quad\quad S(\varphi)=\int_0^{\alpha(\varphi)}\left(1-\frac{\alpha^3r^2}{12F}+\omicron(\alpha^3)\right)^{n-2}\left(\alpha^4+\omicron(\alpha^5)\right)\,da$$

$$(50)$$

$$\quad\quad S(\varphi)=\frac{1}{3}\left(\frac{12F}{r^2n}\right)^{5/3}\left(\int_0^\infty\left(1-\frac{X}{n}\right)^{n-2}x^{2/3}dx+\omicron(1)\right)=\frac{\Gamma\left(\frac{5}{3}\right)}{3}\left(\frac{12F}{r^2n}\right)^{5/3}(1+\omicron(1)).$$

Therefore

$$(51)\quad E_n\sim\Gamma\left(\frac{5}{3}\right)\sqrt[3]{\frac{2n}{3F}}\int^{2\pi}r^{2/3}d\varphi.$$

If now $s$ denotes the arclength on the boundary of $K$ we get, taking $d\varphi/ds=1/r$ into account, the following theorem:

Theorem 3. If $K$ is a convex region whose boundary curve $L$ possesses the continuous curvature $\varkappa=\varkappa(s)$, then it holds true that

$$(52)\quad E_n\sim\Gamma\left(\frac{5}{3}\right)\sqrt[3]{\frac{2}{3}}\left(F^{-1/3}\int_L\varkappa^{1/3}ds\right)\sqrt[3]{n}.$$

​ The integral $\int_L\varkappa^{1/3}ds$ that appears in $(52)$ is just the equi-affine length of curve $L$. One easily sees that the factor of $\sqrt[3]{n}$  even is affine invariant. From the affine isoperimetric property of ellipses (Blaschke-Reidemeister) it follows that that factor is maximal for ellipses and only for those.



§ 4. Normally random distributed points

In this paragraph we prove the following theorem:

Theorem 4.  Let the points $P_i$ ($i=1,\,2,\,\ldots,\,n$) be chosen independently and according to the same normal distribution in the plane, then

$$(53)\quad E_n\sim2\sqrt{2\pi\log n}$$

Proof. As $E_n$ is obviously invariant under affine transformations of the plane, we may assume that the density function of our normal distribution has the form $\frac{1}{2\pi}e^{-\frac{x^2+y^2}{2}}$. As already in the previous paragraph we have

$$\quad E_n=\binom{n}{2}W_n,$$

where $W_n$ is the probability that all points $P_3,\,\ldots,\,P_n$ lie on the same side of the line $P_1\,P_2$. Because of the integralgeometric formula

$$\quad\quad dP_1\,dP_2=dp\,d\varphi\,\left|t_1-t_2\right|\,dt_1\,dt_2$$

and because of the radial symmetry of the normal distribution we get

$$(54)\quad W_n=\frac{1}{2\pi}\iiint\left(g(p)^{n-2}+\left(1-g(p)\right)^{n-2}\right)\left|t_1-t_2\right|e^{-p^2 -\frac{t_1^2+t_2^2}{2}}dt_1\,dt_2\,dp$$

where

$$(55)\quad g(p)=\int_{-\infty}^{+\infty}\int_p^{+\infty}\frac{e^\frac{x^2+y^2}{2}}{2\pi}dx\,dy=1-\Phi(p)$$

has been set and

$$(56)\quad \Phi(p)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^pe^{-\frac{u^2}{2}}du$$

holds.

​ Via the transformation

$$(57)\quad u=\frac{t_1-t_2}{\sqrt{2}},\quad v=\frac{t_1+t_2}{\sqrt{2}},\quad\frac{\partial(t_1,\,t_2)}{\partial(u,\,v)}=1$$

we get

$$(58)\quad \frac{1}{2\pi}\iint\left|t_1-t_2\right|e^{-\frac{t_1^2+t_2^2}{2}}dt_1\,dt_2 =\frac{2}{\sqrt{\pi}}$$

therefore

$$(59)\quad W_n=\frac{2}{\sqrt{\pi}}\int_0^\infty\left[\Phi^{n-2}(p)+\left(1-\Phi(p)\right)^{n-2}\right]e^{-p^2}dp$$

and as obviously $1-\Phi(p)\leqq1/2$ for $p\geqq0$ it follows that

$$(60)\quad W_n\sim\frac{2}{\sqrt{\pi}}\int_0^\infty\Phi^{n-2}(p)e^{-p^2}dp.$$

Now for $p\gt1$

$$(61)\quad\Phi(p)=1-\frac{e^{-\frac{p^2}{2}}}{\sqrt{2\pi}p\left(1+\frac{\theta p}{p^2}\right)}$$

where $0\lt\theta_p\lt1$ (A. Renyi, [3],) p. 136, exercise 18). With the substitution

$$(62)\quad p=\sqrt{2\log n-\log(2\log n)}+\frac{u-\log\sqrt{2\pi}}{\sqrt{2\log n}}$$

one finally gets after some calculations

$$\quad\quad W_n\sim\frac{4\sqrt{2\pi\log n}}{n^2}.$$

Therefore

$$\quad\quad E_n\sim 2\sqrt{2\pi\log n}$$

which had to be proven.



References

[1] Blaschke, W.: Integralgeometrie 3rd edition Berling: VEB Deutscher Verlag der Wissenschaften 1955, 1 - 130.

[2]--, and K. Reidemeister. Differentialgeometrie II, Berlin: Springer 1923, 60.

[3] Rényi, A.: Wahrscheinlichkeitsrechnung, mit einem Anhang über  Informationstheorie. Berlin: VEB Deutscher Verlag der Wissenschaften 1962, 1 - 547

Magyar Tudományos Akadémia Matematikai

Kutató Intézete Reáltanoda u. 13 - 15

Budapest V

and

Humboldt-Universität

Berlin



*(Received November 10th 1962)*