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 second in this series of articles.
Z. Wahrscheinlichkeitstheorie 3, 138-147 (1964)
On the Convex Hull of $n$ Randomly Chosen Points. II
by
A. Rényi and R. Sulanke
Introduction
The present article is a continuation of our work $[1]$. We consider a finite convex region $K$ of the plane. Let $P_i$ ($i=1,\,2,\,\ldots,\,n$$) $ $n$ random points of $K$ which are chosen independently according to the equal distribution. By $H_n$ we denote the convex hull of the $P_i$, by $L_n$ the length of the circumference of $H_n$ and by $F_n$ the area of $H_n$. It is obvious that, as $n\to\infty$, the mathematical expectations $E(L_n)$, resp. $E(F_n)$ approach the circumference $L$, resp. the area $F$ of $K$. The rate of that convergence shall be investigated in the following.
In § 1 initially general formulas for the calculation of $E(L_n)$ and $E(F_n)$ will be established. After that we start with considering the case that $K$ has a sufficiently of continuously differentiable boundary curve, whose curvature $k=k(s)$ is positive and finite: $0\lt k(s)\lt A$ ($s$ denotes arclength).
The approximation formulas that are established in §2 allow us to replace the boundary curve of $K$ in the neighborhood of one of its points by its osculating circle. By means of these formulas we manage in § 3 to determine the asymptotic behavior of $E(L_n)$ and $E(F_n)$. It turns out that the deviations $L-E(L_n)$ and $F-E(F_n)$ both are of the type $\mathrm{const.}\ n^{2/3}+\pmb{0}\left(n^{-1}\right)$; In case of the area the equiaffine length of the boundary of $K$ contributes the most to the constant in the leading term; in case of the circumference however, the functional
$$\quad Q(K)=\int_0^L\left(k(s)\right)^{4/3}ds$$
shows up that apparently hasn't been investigated in geometry. It would be interesting to treat an isoperimetric problem for $Q(K)$.
The investigation of the analogous problems for convex polygons lead to rather confusing calculations. For that reason in § 4 we only consider the case that $K$ is a square. Here it turns out, what is surprising at first sight, that area and circumference exhibit a different asymptotic behavior. While for the circumference of the deviation
$$\quad L-E(L_n)=\mathrm{const.}n^{-1/2}+\pmb{0}(n^{-1})$$
is larger than in the smooth case, we have for the area
$$\quad F-E(F_n)=\mathrm{const.}\frac{\ln n}{n}+\pmb{0}(n^{-1});$$
this approximation is substantially better than the corresponding one for an oval with smooth boundary.
§ 1. Formulas for $E(L_n)$ and $E(F_n)$
Let again $\varepsilon_{ij}=1$ if $i\ne j$ and $\overline{P_i\,P_j}$ is a segment of the boundary of $H_n$, and $\varepsilon_{ij}=0$ else. By $\left|\,P_iP_j\,\right|$ we denote the distance of the points $P_i$, $P_j$. Then it holds true that
$$(1)\quad L_n=\sum_{i\lt j}\left|\,P_iP_j\,\right|\varepsilon_{ij}.$$
From this one immediately obtains $E(L_n)=\binom{n}{2}E\left(\left|\,P_iP_j\,\right|\varepsilon_{ij}\right)$, therefore
$$(2)\quad E(L_n)=\binom{n}{2} \frac{1}{F^n}\int\cdots\int\left|\,P_iP_j\,\right|\varepsilon_{ij}dP_1\,\ldots\,dP_n$$
If we integrate over $P_3\,\ldots,\,P_n$, we have
$$(3)\quad E(L_n) = \binom{n}{2}\frac{1}{F^2}\iint\left|\,P_1P_2\,\right|\left\lbrace\left(1-\frac{f}{F}\right)^{n-2}+\left(\frac{f}{F}\right)^{n-2}\right\rbrace dP_1,dP_2;$$
here $f$ is the smaller area that is cut off of $K$ by the line $g(P_1,\,P_2)$, which implies $f/F\leqq 1/2$. Therefore
$$(4)\quad E(L_n)\sim\frac{\binom{n}{2}}{F^2}\iint\left(1-\frac{f}{F}\right)^{n-2}\left|\,P_1P_2\,\right|dP_1\,dP_2.$$
We now, using the same notation as in $[1],\,(41)$ apply the transformation
$$(5)\quad dP_1\,dP_2=\left|1_1-t_2\right|dt_1\,dt_2\,dp\,d\varphi$$
because $\left|t_1-t_2\right|=\left|P_1P_2\right|$ and
$$(6)\iint_{g(p,\varphi)\cap K}\left|t_1-t_2\right|^2dt_1\,dt_2=\frac{l^4}{6}$$
where $l=l(\varrho,\varphi)$ denotes the length of the chord $g(p,\varphi)\cap K$, we get
$$(7)\quad E(L_n)\sim\frac{\binom{n}{2}}{6F^2}\int_0^{2\pi}\int_0^{p(\varphi)}\left(1-\frac{f}{F}\right)^{n-2}l^4dp\,d\varphi.$$
Here $p(\varphi)$ is the support function of region $K$; we chose as the origin $K$'s center of gravity.
Let now $p(P_i,\,P_j)$ denote the distance of the line $g(P_i,\,P_j)$ from the origin $0$. Then, for the area of $H_n$, we have
$$(8)\quad F_n=\frac{1}{2}\sum_{i\lt j}\varepsilon_{ij}\left|P_i\,P_j\right|p(P_i,\,P_j).$$
By conclusions that are close analogues to those as in the case of the circumference, we get
$$(9)\quad E(F_n)\sim\frac{\binom{n}{2}}{12F^2}\int_0^{2\pi}\int_0^{p(\varphi)}\left(1-\frac{f}{F}\right)^{n-2}l^4p\,dp\,d\varphi.$$
§ 2. The approximation by an osculating circle
Our task is now to evaluate the integrals $(7)$ and $(9)$. In this and in the following paragraph we assume that $K$ has a smooth boundary with curvature $k(s),\ 0\lt k(s)\lt A$. We first fix $\varphi$ and carry out the integration over $p$. As for the asymptotic behavior of the integrals only that contribution is important, for which $f/F$ is small, we may replace the values $l,\, f$ of $K$ with the corresponding values $\bar l,\,\bar f$ of the osculating circle, that shares the tangent $g\left(p(\varphi),\,\varphi\right)$ with $K$, The error that is generated by that replacement shall now be estimated. This will yield improvements of the formulas $[1](47)$.
Instead of $p$ we now introduce the new parameter $\beta$, which is half the central angle from the center $Z$ of the osculating circle$S_{\varphi}$ onto the chord $g(p,\,\varphi)\cap S_{\varphi}$. Then we have (cmp. fig. 1)
$$\quad p=r(\cos \beta\, -\, 1)+p(\varphi).$$
Here $r$ denotes the radius of curvature: $r=1/k$. On the line $g(\beta,\varphi)$ we introduce the arc length $t$ as a parameter and denote by $t_1^-,\,t_1^+$ 1the parameters of the intersection points of $g$ with the boundary of $K$. If we chose the center of the chord $g\cap S_{\varphi}$ as the zero-point of the arc length $t$ then it follows immediately that
$$(11)\quad t_1^-=-r\sin\beta,\ t_1^+=r\sin\beta$$.
We now want to calculate $t_2^-,\,t_2^+$ as functions of $\beta$. For that purpose we represent the boundary of $K$ in a neighborhood of the considered point in the acompanying bipod (i.e. in the Frenet frame). Let $\mathfrak{x}(s)$ be the local vector of a variable point of the the boundary curve from the point of contact, $\mathfrak{t}$ a tangent vector and $\mathfrak{n}$ the normal vector in that point. If we chose the point of contact also as the zero-point of the boundary curve's arc length $s$, then, taking ito account the Frenet formulas of planar differential geometry, Taylor's formula yields the following representation:
$$\quad\quad\mathfrak{x}=\mathfrak{t}\cdot\left\lbrace s-k^2\frac{s^3}{3!}-3k\,k'\frac{s^4}{4!}+\pmb{0}(s^5)\right\rbrace+$$
$$(12)$$
$$\quad\quad+\mathfrak{n}\left\lbrace k\frac{s^2}{2!}+k'\frac{s^3}{3!}+(k''-k^3)\frac{s^4}{4!}+\pmb{0}(s^5)\right\rbrace.$$
Here the coefficients have to be taken at $s=0$; apostrophes denote differentiation w.r.t. arc length.
In this coordinate system the line $g(\beta,\varphi)$ has the parametric representation
$$(13)\quad \mathfrak{z}(t)=\mathfrak{t}\cdot t+\mathfrak{n}\cdot r(1-\cos\beta).$$
The comparison with $(12)$ provides us with the following two relations
$$(14)\quad t_2=s-k^2\frac{s^3}{3!}-3k\,k'\frac{s^4}{4!}+\pmb{0}(s^5).$$
$$(15)\quad r(1-\cos\beta)=k\frac{s^2}{2!}+k'\frac{s^3}{3!}+(k''-k^3)\frac{s^4}{4!}+\pmb{0}(s^5).$$
From $(15)$ we obtain $s$ as a function of $\beta$:
$$(16)\quad s=r\beta-\frac{k'r^3\beta^2}{3!}\beta^2+\frac{r^4}{4!}\left\lbrace\frac{5}{3}k'^2r-k''\right\rbrace\beta^3+\pmb{0}(\beta^4);$$
If we insert that in $(14)$, it follows that
$$(17)\quad t_2=r\beta-\frac{k'r^3}{3!}\beta^2+\left\lbrace\frac{5}{4!3}r^5k'^2-\frac{r^4k''}{4!}-\frac{r}{3!}\right\rbrace\beta^3+\pmb{0}(\beta^4);$$
where obviously $t^-=t_2(-\beta),\ t_2^+=t_2(\beta)$ for $\beta\geqq0$. The power series expansion of $\sin\beta$ and $(11)$ yield
$$(18)\quad t_1-t_2=\frac{k'r^3}{3!}\beta^2+\frac{r^4}{4!}\left\lbrace k''-\frac{5}{3}rk'^2\right\rbrace\beta^3+\pmb{0}(\beta^4);$$
Here again we get $t_1^+-t_2^+$ for positive $\beta$ and $t_1^--t_2^-$ for negative $\beta$.
Now we take into account that the osculating circle of a curve in a point that isn't a vertex point, for which therefore $k'\ne0$, intersects the curve in the tangent point, as is also shown in our illustration. That implies $l-\bar l=(t_1^--t_2^-) -(t_1^+-t_2^+) $, consequently
$$(19)\quad l-\bar l=\frac{r^4}{12}\left(\frac{5}{3}rk'^2-k''\right)\beta^3+\pmb{0}(\beta^4).$$
Because $k'=0$ in a vertex point and there is a contact of at least third order with the osculating circle, $(19)$ is valid even more in that case; that can be seen immediately from $(18)$.
For the areas $f,\ \bar f$ we get from evaluating the integral
$$\quad f-\bar f=\int_p^{p(\varphi)}(l-\bar l)dp
the following approximation formula:
$$(20)\quad f-\bar f=\frac{r^5}{60}\left(\frac{5}{3}r\,k'2-k''\right)\beta^5+\pmb{0}(\beta^6).$$
§ 3. Calculation of $E(L_n)$ and $E(F_n)$ for an oval region with smooth boundary
We switch to the central angle $\alpha=2\beta$ and express the Integrals $(7)$ and $(9)$ via $\alpha$ and $\varphi$. Because of
$$(21)\quad l=2r\sin\frac{\alpha}{2}\quad\text{and}\quad\bar f= \frac{r^2}{2}(\alpha-\sin\alpha)$$
as well as
$$(22)\quad\left|dp\right|=\left(\frac{r}{2}\sin\frac{\alpha}{2}\right)\left|d\alpha\right|$$
$(19)$ yields
$$(23)\quad l^4dp=\left[\frac{r^5\alpha^5}{4}\left(1+G\alpha^2\right)+\pmb{0}(\alpha^8)\right]d\alpha$$
where we have set
$$(24)\quad G=\frac{5}{4!}\left(\frac{r^4r'^2}{3}-\frac{r^3k''}{5}-1\right)$$
for abbreviation. From $(20)$ and $(21)$ we get
$$(25)\quad \frac{f}{F}=\frac{r^2\alpha^3}{12F}+\varkappa\cdot\alpha^5+\pmb{0}(\alpha^5)$$
where
$$(26)\quad\varkappa=\frac{r^2}{5!2\,F\,}\left[\left(\frac{r}{3}\right)^3\left(\frac{5}{3}rk'^2-k''\right)-1\right].$$
The integral $(7)$ now attains the form
$$\quad\quad E(L_n)\sim\frac{\binom{n}{2}}{4!\,F^2}\int_0^{2\pi}r^5\,d\varphi\int_0^{\alpha(\varphi)}\left(1-\frac{r^2\alpha^3}{12F}-\varkappa\alpha^5-\pmb{0}(\alpha^6)\right)^{n-2}\times$$
$$(27)$$
$$\quad\quad\times(\alpha^5+G\alpha^7+\pmb{0}(\alpha^8))d\alpha$$
We first calculate the integrals
$$(28)\quad B_\nu=\int_0^{\alpha(\varphi)}\left(1-\frac{r^2\alpha^3}{12F}-\varkappa\alpha^5-\pmb{0}(\alpha^6)\right)^{n-2}\alpha^\nu\,d\alpha.$$
Via the substitution
$$(29)\quad\frac{r^2\alpha^3}{12F}=\frac{x}{n}$$
we get, taking into account
$$(30)\quad\left(1-\frac{x}{n}-\varkappa_1\left(\frac{x}{n}\right)^{5/3}+\pmb{0}\Big(\left(\frac{x}{n}\right)^2\right)^{n-2}=e^{-x}\left(1-\frac{\varkappa_1x^{5/3}}{n^{2/3}}+\pmb{0}\left(\frac{x^2}{n}\right)\right)$$
the integral $B_\nu$ in the form
$$(31)\quad B_\nu=\frac{1}{3}\left(\frac{12F}{n\,r^2}\right)^{(\nu+1)/3}\int_0^{nr^2\alpha^3(\varphi)/12F}e^{-x}\left(1-\varkappa_1x^{5/3}n^{-2/3}+\pmb{0}\left(\frac{x^2}{n}\right)\right)x^{(\nu-2)/3}dx.$$
where
$$(32)\quad\varkappa_1=\varkappa\left(\frac{12\,F}{r^2}\right)^{5/3}$$
has been set. If we now integrate in $(31)$ not only to the upper bound that has been given here, but to $+\infty$, we introduce an error of exponential order of magnitude that is neglegible. It follows that
$$(33)\quad B_\nu=\frac{1}{3}\left(\frac{12\,F}{n\,r^2}\right)^{(\nu+1)/3}\cdot\left[\Gamma\left(\frac{\nu+1}{3}\right)-\frac{\varkappa_1}{n^{2/3}}\Gamma\left(\frac{\nu}{3}+2\right)\right]+\pmb{0}\left(n^{-(\nu+4)/3}\right).$$
By inserting $(33)$ into $(27)$ we get
$$(34)\quad E(L_n)=L-a(K)n^{-2/3}+\pmb{0}\left(\frac{1}{n}\right).$$
The constant $a(K)$ results from calculating
$$(35)\quad a(K)=\Gamma\left(\frac{11}{3}\right)\int_0^{2\pi}\varkappa_1\,r\,d\varphi-(12\,F)^{2/3}\Gamma\left(\frac{8}{3}\right)\int_0^{2\pi}Gr^{-1/3}d\varphi$$
taking into account $(24)$, $(26)$ and $(32)$ in the form
$$(36)\quad a(K)=\frac{(12\,F)^{2/3}\Gamma\left(\frac{8}{3}\right)}{4!}\int_0^L\left[\frac{9}{5}k^{4/3}+\frac{3}{5}k''k^{-5/3}-k'^{\,2}k^{-8/3}\right]ds.$$
Here, instead of $\varphi$, the arclength $s$ of the boundary curve of $K$ has been introduced as the parameter; as it is valid that $d\varphi=k\,ds$. By partial integration it follows that
$$(37)\quad\frac{3}{5}\int_0^Lk''\,k^{-5/3}ds=\int_0^Lk'^{\,2}k^{-8/3}ds.$$
Therefore, for $a(K)$ we finally get
$$(38)\quad a(K)=\frac{1}{12}\Gamma\left(\frac{2}{3}\right)(12\,F)^{2/3}\int_0^Lk^{4/3}ds.$$
For the calculation of $E(F_n)$ we also carry out the substitution $(22)$ and get
$$\quad\quad E(F_n)\sim\frac{\binom{n}{2}}{12\,F}\int_0^{2\pi}\int_0^{\alpha(\varphi)}\left(1-\frac{r^2\alpha^3}{12\,F}-\varkappa\alpha^5-\pmb{0}(\alpha^6)\right)^{n-2}\times$$
$$(39)$$
$$\quad\quad\times\left[\frac{p(\varphi)r^5\alpha^5}{4}+\left(\frac{Gp(\varphi)r^5}{4}-\frac{r^5}{32}\right)\alpha^7+\pmb{0}(\alpha^8) \right]d\alpha\,d\varphi.$$
According to $(33)$ that yields
$$(40)\quad E(F_n)=F-b(K)n^{-2/3}+\pmb{0}(n^{-1})$$
For the costant $b(K)$ we first find after some calculations
$$(41)\quad b(K)=\frac{1}{16}\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}\sigma(K)+c(K);$$
where
$$(42)\quad\sigma(K)=\int_0^Lk^{1/3}ds$$
is the equi affine arclength of the boundary curve of $K$, while $c(K)$ is of the form
$$(43)\quad c(K)=\frac{\Gamma\left(\frac{8}{3}\right)}{4!}(12\,F)^{2/3}\int_0^{2\pi}p\,r^{-1/3}\left(\frac{9}{10}+\frac{3}{10}r^3k''-\frac{1}{2}r^4k'^{\,2}\right)d\varphi.$$
By a dot above we now denote derivations with respect to $\varphi$ and express $k',\,k''$ via $r,\,\dot r,\,\ddot r$. It follows
$$(44)\quad c(K)=\frac{\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}}{4!\,10}\int_0^{2\pi}p(9\,r^{-1/3}+4\dot r^2\, r^{-7/3}-3\ddot r\, r^{-4/3})\,d\varphi$$
By integrating partially twice, we get
$$(45)\quad \int_0^{2\pi}(4\,\dot r^2r^{-7/3}-3\ddot r r^{-4/3})p\,d\varphi=9\int_0^{2\pi}r^{-1/3}\ddot p\,d\varphi.$$
We now substitute that into $(44)$. Because $p+\ddot p = r$ (cf e.g. W. Blaschke $[2]$, $p. 30$) that again yields a multiple of $\sigma(K)$. Taking into account $(41)$ finally yields
$$(46)\quad b(K)=\frac{1}{10}\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}\sigma(K).$$
The results of this paragraph can be summarized as follows:
Theorem 1. Let $K$ be a planar, finite convex region whose boundary curve is sufficiently often continuously differentiable. The curvature $k(s)$ of the boundary shall satisfy the inequality $0\lt k(s)\lt A$. Let $L$ be the circumference and $F$ the area of $K$. The length $L_n$ of the convex hull $H_n$ of $n$ points in $K$ that are chosen independently and according to equal distribution, possesses the mathematical expectation
$$(47)\quad E(L_n)=L-\frac{\Gamma(2/3)(12\,F)^{2/3}\int_0^Lk^{4/3}ds}{12\,n^{2/3}}+\pmb{0}(n^{-1}).$$
For the mathematical expectation of the area $F_n$ of $H_n$ we have
$$(48)\quad E(F_n)=F-\frac{\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}\sigma(K)}{10^{2/3}}+\pmb{0}(n^{-1})$$
where $\sigma(K)$ according to* $(42)$ denotes the equiaffine length of the boundary of $K$
§ 4. Calculation of $E(L_n)$ and $E(F_n)$ for a square
Let $K$ now be a square with side length $a$. We place the coordinate origin in the center of $k$ and the null-direction $\varphi=0$ shall go from $\pmb{0}$ to the center of a side. We have to evaluate the integrals $(7)$ and $(9)$ again. For reasons of symmetry it is sufficient to carry out the integration over $\varphi$ from $0$ to $\pi/4$ and multiply by $8$ accordingly. For the integration over $p$ we distinguish two cases. 1. the line $g(\varrho\,\varphi)$ hits two opposite sides of the square. That happens if
$$(49)\quad 0\leqq p\leqq p_1(\varphi)=\frac{a}{2}(\cos\,\varphi-\sin\,\varphi)$$
holds true. For $l$ and $f$ this implies
$$(50)\quad l=l(\varphi)=\frac{a}{\cos\,\varphi}, \quad f=f(p,\,\varphi)=\frac{a^2}{2}-\frac{ap}{\cos\,\varphi}$$
\2. the line $g(p,\,\varphi)$ hits two adjacent sides of the square. In that case we have
$$(51)\quad p_1(\varphi)\leqq p\leqq p(\varphi)=\frac{a}{2}(\cos\,\varphi+sin\,\varphi).$$
Further we have
$$(52)\quad l=l(p,\,\varphi)=\frac{p(\varphi)-p}{\cos\,\varphi\,\sin\,\varphi},\quad f=f(p,\,\varphi)=\frac{\left(p(\varphi)-p\right)^2}{2\,\sin\,\varphi\,\cos\,\varphi}.$$
Because of this distinction of cases the integrals $(7)$ and $(9)$ appear now as sums
$$(53)\quad E(L_n)\sim I_1+I_2,\quad E(F_n)\sim J_1+J_2$$
and we have to evaluate the following four expressions:
$$(54)\quad I_1=\frac{4}{3}\binom{n}{2}\_0^{\pi/4}\int_0^{p_1(\varphi)}\left(\frac{1}{2}+\frac{p}{a\,\cos\,\varphi}\right)^{n-2}\frac{dp\,d\varphi}{\cos^4\varphi},$$
$$(55)\quad I_2=\frac{4\,\binom{n}{2}}{3\,a^4}\int_0^{\pi/4}\int_{p_1(\varphi)}^{p(\varphi)}\left(1-\frac{\left(p(\varphi)-p\right)^2}{2a^2\sin\,\varphi\,\cos\,\varphi}\right)^{n-2}\frac{\left(p(\varphi)-p\right)^4dp\,d\varphi}{\cos^4\varphi\,\sin^4\varphi},$$
$$(56)\quad J_1=\frac{2}{3}\binom{n}{3}\int_0^{\pi/4}\int_0^{p_1(\varphi)}\left(\frac{1}{2}-\frac{p}{a\,cos\varphi}\right)^{n-2}\frac{p\,dp\,d\varphi}{\cos^4\varphi}.$$
$$(57)\quad J_2=\frac{2\,\binom{n}{2}}{3\,a^4}\int_0^{\pi/4}\int_{p_1(\varphi)}^{p(\varphi)}\left(1-\frac{\left(p(\varphi)-p\right)^2}{2\,a^2\,\sin\,\varphi\,\cos\,\varphi}\right)^{n-2}\frac{\left(p(\varphi)-p\right)^4p\,dp\,d\varphi}{\cos^4\varphi\,sin^4\,\varphi}.$$
We now start with the calculation of $I_1$. Substituting
$$(58)\quad p=x\,a\,\cos\,\varphi$$
yields
$$(59)\quad I_1=\frac{2\,n\,a}{3}\int_0^{\pi/4} \frac{(1-\frac{1}{2}\,tg\,\varphi)^{n-1}}{\cos^3\,\varphi}+\pmb{0}(2^{-n}).$$
If we now substitute
$$(60)\quad tg\,\varphi=t$$
we get $I_1$ in a form that is easy to estimate. It results
$$(61)\quad I_1=\frac{4\,a}{3}+\pmb{0}\left(\frac{1}{n^2}\right).$$
Now we calculate $I_2$. With the substitution
$$(62)\quad \frac{\left(p(\varphi)-p\right)^2}{2\,a^2\,\sin\,\varphi\,\cos\,\varphi}=\frac{x}{n}$$
we have
$$(63)\quad I_2=\frac{2^{5/2}\cdot a(n-1)}{3\,n^{3/2}}\int_0^{\pi/4}(\cos\,\varphi\,\sin\varphi)^{-3/2}\left[\int_0^{(n\,tg\,\varphi)/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\right]\,d\varphi.$$
Now substitute
$$(64)\quad n\,tg\,\varphi = z$$
and get
$$(65)\quad I_2=\frac{2^{5/2}\cdot a(n-1)}{3\,n}\int_0^n\left(\frac{1+\frac{z^2}{n^2}}{z^3}\right)^{1/2}\int_0^{z/2}\left(1-\frac{x}{n}\right)\,x^{3/2}dx\,dz\,.$$
We set
$$(66)\quad\left(1+\frac{z^2}{n^2}\right)^{1/2}=\left[\left(1+\frac{z^2}{n^2}\right)^{1/2}-1\right]+1$$
and thus partition the integral $(65)$ into two components. With the substitution $z=n\,\tau$ we get for the first part:
$$(67)\quad \frac{2^{5/2}\cdot a(n-1)}{3\,n}\int_0^n\frac{\sqrt{1+\frac{z^2}{n^2}}-1}{z^{3/2}}\int_0^{z/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\,dz=\sqrt{\frac{2\pi}{n}}\,aq+\pmb{0}\left(\frac{1}{n}\right)$$
where
$$(68)\quad q=\int_0^1\frac{\sqrt{1+\tau^2}\,-1}{\tau^{3/2}}d\tau$$
For the second part we obtain after several elementary rearrangements
$$(69)\quad\frac{2^{5/2}\cdot a(n-1)}{3\,n}\int_0^n\left(\int_0^{z/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\right)\frac{dz}{z^{3/2}}=\frac{8\,a}{3}-2\sqrt{\frac{2\pi}{n}}\cdot a+\pmb{0}\left(\frac{1}{n}\right)\,.$$
From $(61)$, $(67)$ and $(69)$ we get for the mathematical expectation of $L_N$
$$(71)\quad E(L_n)=4\,a\,-\,\frac{a\,(2-q)\sqrt{2\pi}}{\sqrt{n}}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
For the calculation of $J_1$ one again applies the transformations $(58)$ and after that $(60)$. After some elementary calculations one gets
$$(71)\quad J_1=\frac{1}{3}a^2+\pmb{0}\left(\frac{1}{n}\right)\,.$$
Finally, we also have to calculate the integral $J_2$. The substitution $(62)$ leads to $J_2=R_1-R$ with
$$(72a)\quad R_1=\frac{4\,a^2(n-1)}{3\,n^{3/2}}\int_0^{\pi/4}\frac{\cos\,\varphi+\sin\varphi}{(\sin\,2\,\varphi)^{3/2}}\left(\int_0^{(n\,tg\,\varphi)/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\right)\,d\varphi,$$
$$(72b)\quad R=\frac{8\,a^2(n-1)}{3\,n^2}\int_0^{\pi/4}\left[\int_0^{(n\,tg\,\varphi)/2}\left(1-\frac{x}{n}\right)^{n-2}x^2\,dx\right]\frac{d\varphi}{\sin\,2\,\varphi}\,.$$
The calculation of $R_1$ is easily possible via the substitution $(64)$. It results in
$$(73)\quad R_1=\frac{2}{3}\,a^2+\pmb{0}\left(\frac{1}{n}\right)\,.$$
For $R$ we get via the substitution
$$(74)\quad\frac{n\,tg\,\varphi}{2}=t$$
the expression
$$(75)\quad R=\frac{4\,a^2(n-1)}{3\,n^2}\int_0^{n/2}\left(\int_0^t\left(1-\frac{x}{n}\right)^{n-2}x^2dx\right)\frac{dt}{t}\,.$$
If we integrate over $x$, this yields
$$(76)\quad R=\frac{8\,a^2}{3(n+1)}\int_0^{n/2}\left[1-\left(1-\frac{t}{n}\right)^{n+1}\right]\frac{dt}{t}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
For calculating the integral that appears in $(76)$ we use the formula
$$(77)\quad\frac{1}{t}\left[1-\left(1-\frac{t}{n}\right)^{n+1}\right]=\sum_{k=0}^n\left(1-\frac{t}{n}\right)^k\,.$$
It follows
$$(78)\quad \int_0^{n/2}\left[1-\left(1-\frac{t}{n}\right)^{n+1}\right]\frac{dt}{t}=\ln\,n+C-\log\,2+\pmb{0}\left(\frac{1}{n}\right)\,.$$
here $C$ is the Euler constant. This results in
$$(79)\quad J_2=R_1-R=\frac{2a^2}{3}-\frac{8\,\ln\,n}{3\,n}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
If we take into account formula $(70)$ and $E(F_n)=J_1+J_2$, we can summarize the results of this paragraph in the following theorem:
Theorem 2. In a square $K$ with sidelength $a$ let $H_n$ denote the convex hull of $n$ points chosen independently and equally distributed from $K$. For the mathematical expectation of the circumference $L_n$ of $H_n$ it is valid that
$$(80)\quad E(L_n)=4\,a-\frac{a(2-q)\sqrt{2\pi}}{\sqrt{n}}+\pmb{0}\left(\frac{1}{n}\right)$$
where the constant $q$ is given by $(68)$. For the mathematical expectation of the area $F_n$ of $H_n$ it is valid that
$$(81)\quad E(F_n)=a^2-\frac{8\,a^2\,\ln\,n}{3\,n}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
References
$[1]$ Rényi, A. u. R. Sulanke: Über die konvexe Hülle von $n$ zufällig gewählten Punkten,
Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2 (1963) 75-84.
$[2]$ Blaschke, W.: Vorlesungen über Integralgeometrie, 3. Aufl., Berlin, VEB Deutscher Verlag der Wissenschaften, 1955.
Budapest, VI, Hungary Benczur u.28
and
Schulzendorf upon Eichwalde near Berlin
Hamburger Straße 4
(Received on 7th October 1963)
Hope to add bits of mathematics or mathematical news I find interesting.
Showing posts with label convex hulls of random points. Show all posts
Showing posts with label convex hulls of random points. Show all posts
Tuesday, December 3, 2019
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)*
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)*
Subscribe to:
Posts (Atom)