Z. Wahrscheinlichkeitstheorie verw. Geb. 9, 146-157 (1968)
Random Convex Polygons in a Ring-shaped Region
by
A. Rényi and R. Sulanke
Received June 2nd 1967
1. Introduction
Let $K$ be a non-degenerated, finite convex region of the Euclidean plane and $B$ an arbitrary convex region that is contained in the interior of $K$. We chose $n$ random lines $g_1,\,\ldots,\,g_n$ that intersect $K$ but not $B$.
The $g_i$ shall be independent; their distribution shall be the Euclidean invariant line measure $\mu$ with density $dg$ (W. Blaschke $[1]$, § 2). By $H_i$ we denote the closed halfplane defined by $g_i$ that contains $B$. Then
$$(1.1)\quad\Pi_n=\cap_{i=1}^nH_i$$
is a random convex polygon that contains $B$ and is uniquely defined by the $g_i$. By $X_n$ we denote the number of corners of $\Pi_n$. We want to determine the asymptotic behavior of the mathematical expectation of the number of corners of $X_n$ under various assumptions on $B$.
In § 2 we establish the formulas for the probabilities that are to be investigated and derive some simple estimates that will be applied in §§ 3-5. Further we show that the probability for $\Pi_n$ not being closed, as well as the probability that $\Pi_n$ isn't contained in $K$ is of the order $O(\gamma^n)\ (0\lt\gamma\lt 1)$ tends to zero. In § 3 we consider the case that $B$ degenerates to a point and prove $E(X_n)\to\frac{\pi^2}{2}$ for $n\to+\infty$.
In the case that $B$ has a smooth boundary of limited curvature it holds true that $E(X_n)\sim \mathrm{const}.\,n^{1/3}$(theorem 4. § 4); if finally $B$ is a convex $r$-gon ($r\geqq2$; $r=2$ means that $B$ degenerates to a line segment ), that yields $E(X_n)\sim\frac{2}{3}r\,\log\,n$ (theorem 5, § 5). The order of magnitude with which $E(X_n)$ tends to infinity with $n$ in the last two cases therefore complies with the corresponding orders of magnitude for the case of the corners of the convex hull of $n$ points that are randomly chosen in $B$ (A. Rényi, R. Sulanke $[2]$).
We would like to warmly thank Mr. L. Berg for some hints to the calculations in § 5.
The result of § 3 may be interpreted as follows: We consider a system of $n$ random linear inequalities $a_kx+b_ky\leqq c_k$ ($k =1,\,2,\,\ldots,\,n$). The word "random" shall mean that the distribution of the lines $a_kx+b_ky=c_k$, that are independent from each other and that all shall hit the region $K$, is determined by the invariant line-measure and the point $B(x=0, y=0)\in K$ satisfies all inequalities. Let $X_n$ be the smallest number with the following property: There are $X_n$ of the inequalities such that every point $(x,y)$, that satisfies these $X_n$ inequalities, even satisfies all $n$ inequalities. Our result says that for $n\to\infty$ the expected value of the minimal number $X_n$ of the "critical" inequalities approaches $\pi^2/2$. Therefore one can expect that the solutionto a problem from linear programming with two unknowns and arbitrarily large number of linear inequalities with random data requires on average only a rather small number of steps when following one of the known procedures. So naturally the problem comes up, to treat the analogous task for an arbitrary number of unknowns ( that is for the intersection of random halfspaces of a $k$-dimensional space, $k=3\,,4\,\ldots$). That task was solved recently by Mr. Wolfgang M. Schmidt, when he proved that the average minimal number of "critical" inequalities, also in the $k$-dimensional case ($k=3,\,4,\,\ldots$) approaches a finite value $\lambda_k$ that only depends on $k$; but his prove only yields the existence of the numbers $\lambda_k$ and not their exact value. From the theorem of Mr. Wolfgang M. Schmidt follows the existence of the limit distribution of $X_n$ for the two-dimensional case that we consider. We hope to return to the explicit determination of that limit distribution in another work.
2. Basic formulas and simple estimations
Let $S_{ij}=g_i\cap g_j\ (i\ne j)$. The point $S_{ij}$ exists with probability 1.
If we now set $\varepsilon_{ij}=1$ if $S_{ij}$ is a corner of $\Pi_n$ and $\varepsilon_{ij}=0$ else, then it holds true that
$$(2.1)\quad X_n=\sum_{1\leqq i\lt j\leqq}\varepsilon_{ij}.$$
Let $W\,(n)$ be the probability for $S_{12}$ being a corner of $\Pi_n$. For reasons of symmetry the mathematical expectation turns out to be
$$(2.2)\quad E(X_n)=\binom{n}{2}\,W\,(n).$$
We first want to derive a general formula for $W\,(n)$. The point $S=S_{12}$ is a corner of $\Pi_n$ exactly if none of the lines $g_3,\,\ldots,\,g_n$ hits the convex hull $B_S$ of $B\cup S$. Let $l$ be the circumference of $K$, $b$ the one of $B$ and $l_S$ the one of $B_S$. According to Crofton's formula for convex regions (W. Blaschke $[1]$, § 3, (60))
$$(2.3)\quad \int_{g\,\cap K\ne\emptyset}dg=l$$
yields for the case $S\in K$
$$(2.4)\quad P\left(g_3\,\cap B_S\ne\emptyset\right)=\frac{l-l_S}{l-b}.$$
We decompose $W\,(n)$ into the two probabilities
$$(2.5)\quad W\,(n) = W_1(n)+W_2(n),$$
$$ (2.6)\quad W_1(n) = P\left(S\ \mathrm{corner\ of}\ \Pi_n,\, S\in K\right),$$
$$ (2.7)\quad W_1(n) = P\left(S\ \mathrm{corner\ of}\ \Pi_n,\, S\notin K\right).$$
It holds true that
$$(2.8)\quad W_1=\frac{1}{(l-b)^n}\iint_{g_1\,\cap\,g_2\,\cap \,K\ne\emptyset,\ (g_1\,\cup \,g_2)\cap B=\emptyset}(l-l_S)^{n-2}dg_1\,dg_2.$$
For $W_2(n)$ we give an estimation from which it will follow that $W_2(n)$ will be neglegible compared to $W_1(n)$. If $\mu$ denotes the line-measure then that yields
$$(2.9)\quad W_2\,(n)=\frac{1}{(l-b^n)}\iint_Df(S)^{n-2}dg_1\,dg_2$$
with $f(S)=\mu(g:\,g\,\cap\,B_S=\emptyset,\ g\,\cap\,K\ne\emptyset)$. Integration is over the region $D$ of all line-pairs $g_1,\,g_2$ with $g_1\cap\,K\ne\emptyset,\,g_2\,\cap\,K\ne\emptyset,\,g_1\,\cap\,g_2\,\cap\,K=\emptyset,\,(g_1\,\cup\,g_2)\,\cap\,B=\emptyset$. In order to estimate $f(S)$ we chose a boundary point $R$ of $K$ that lies in $B_S$; then $B_R\subset B_S$ and consequently
$$(2,10)\quad f(S)\leqq f(R)=l-l_R=(l-b)-(l_R-b).$$
By cutting off from $B_R$ by means of an appropriate support-line (i.e. tangent to the boundary) and isosceles triangle (fig. 1) we get
$$(2.11)\quad l_R-b\geqq 2a-c=2a\left(1-\sin\frac{\varphi}{2}\right).$$
If $r$ denotes the distance of the boundaries of $B$ and $K$, then obviously $a\geqq r\gt 0$; further we have, if $\varphi$ is the angle under which $B$ is seen from a boundary point of $K$, $0\leqq\varphi\leqq\varphi_0\le\pi$; because lies completely inside the inner of $K$. So it holds true that
$$(2.12)\quad l-l_b\geqq l_R-b\geqq2r\left(1-\sin\frac{\varphi_0}{2}\right)=\varepsilon\gt 0.$$
From $(2.10)$ and $(2.12)$ follows
$$(2.13)\quad\frac{f(S)}{l-b}\leqq\frac{l-b-\varepsilon}{l-b}=\gamma\ \text{with}\ 0\lt\gamma\lt 1,$$
where $\gamma$ only depends on $B$ and $K$. We get
$$(2.14)\quad W_2(n)=\frac{\gamma^{n-2}}{(l-b)^2}\iint_{\begin{matrix}g_1\,\cap\,K\ne \emptyset,\,g_2\,\cap\,K\ne\emptyset \\ g_1\,\cap\,g_2\,\cap\,K=\emptyset \end{matrix}}dg_1\,dg_2.$$
After a formula of Crofton (W.Blaschke, $[1]$, § 7 ) one gets for the integral $(2.14)$
$$(2.15)\quad\iint\,dg_1\,dg_2 =l^2-2\,\pi\,F$$
where $F$ is the area of $K$. It follows
$$(2.16)\quad W_2(n)=O(\gamma^n)\quad\mathrm{with}\quad 0\lt\gamma\lt1 \,.$$
If the region $B$ degenerates to a point, one gets $(2.16)$ by an even simpler estimation. The thoughts show in general that the portion of line-pairs $g_1,\,g_2$, whose intersection point $S$ lies outside a fixed convex neighborhood $U$ of $B$, is of the order of magnitude $O(\gamma^n)$ where $\gamma$ with $0\lt\gamma\lt 1$ of course depends on the neighborhood $U$.
Theorem 1. Let $B$ be a ( possibly degenrate ) convex region and $K$ a convex neighborhood of $B$. The probability for a corner of $\Pi_n$ to lie outside of $K$ satisfies the relation
$$(2.17)\quad P(\,\mathrm{corner}\ \mathrm{of}\ \Pi_n\notin K )=O(\gamma^n)\quad(0\lt\gamma\lt 1)$$
where $\gamma$ is a constant depending on $K$ and $B$.
It remains to evaluate $(2.8)$. To this end we carry out, after W. Blaschke $[1]$, § 6, (89), the substitution
$$(2.18)\quad dg_1\,dg_2=\left|\sin(\varphi_1-\varphi_2)\right|\,d\varphi_1\,d\varphi_2\,dS\,;$$
here $\varphi_1$, $\varphi_2$ are the angles of $g_1$, resp. $g_2$ with a given fixed direction and, $dS$ the density of the intersection point $S=g_1\cap\,g_2$. Because
$$(2.19)\quad\int_0^\alpha\int_0^\alpha\left|\sin(\varphi_1-\varphi_2)\right|\,d\varphi_1\,d\varphi_2\,dS=2(\alpha-\sin\,\alpha)$$
we get, because we have to integrate over $\psi_1\leqq\varphi_1,\,\varphi_2\leqq\psi_2$,
$$(2.20)\quad W_1(n)=\frac{2}{(l-b)^2}\int_{S\in K\setminus B}\left(1-\frac{l_S-b}{l-b}\right)^{n-2}\left(\alpha(S)-\sin\alpha(S)\right)\,dS\,;$$
here $\alpha=\psi_2-\psi_1=\pi-\omega$ and $\omega$ is the angle under which $B$ is seen from $S$ ($fig.\ 2$). The evaluation of the integral under various preconditions on $B$ is carried out in §§ 3-5.
$$fig.\ 2$$
Before that, we investigate the probability for $\Pi_n$ not being closed. It could be suspected that the polygon $\Pi_n$ doesn't enclose region $B$ also for larger $n$, i.e. isn't finite. That will happen particularly if $B$ comes close to the boundary of $K$ only at one side. Of course the probability that $\Pi_n$ isn't closed tends for $n\to\infty$ towards zero. We now want to estimate the order of magnitude of this convergence.
Let $\varphi_i$ be the angle of the normals of $g_i$, that are directed away from $B$, with a fixed direction. By $\psi_i$ we denote the ordered sample of the $\varphi_i$, i.e. the $\psi_i$ as well as the $\varphi_i$ are ordered according to magnitude: $0\leqq\psi_1\leqq\psi_2\leqq\cdots\leqq\psi_n\le 2\pi$. Let $\delta_i=\psi_i-\psi_{i-1}$ ($i=1,\,\ldots,\,n$), where $\psi_0=\psi_n-2\pi$ shall be set. The polygon is not closed exactly if one of the angles $\delta_i\geqq\pi$ is. Consequently we first have to calculate the distribution function of the angle $\varphi$ under the condition $g\,\cap\,K\ne\emptyset,\ g\,\cap\,B=\emptyset$. If $p_0(\varphi)$ is the support function of $B$ and $p_1(\varphi)$ the one of $K$, then it follows for $0\leqq x\leqq2\pi$
$$(2.21)\quad P(\varphi\leqq x)=\frac{1}{l-b}\int_0^x\int_{p_0(\varphi)}^{p_1(\varphi)}dp\,d\varphi=\frac{1}{l-b}\int_0^x\left(p_1(\varphi)-p_0(\varphi)\right)\,d\varphi\,.$$
This implies: If $p_1(\varphi)-p_0(\varphi)=r$ is constant, i.e. $K$is the outer parallel region at distance $r$ from $B$, then $\varphi$ is equally distributed on the unit circle and it holds true that
$$(2.22)\quad l-b=2\pi r$$
In this case the density of $\varphi$
$$(2.23)\quad f(\varphi)=\frac{p_1(\varphi)-p_(\varphi)}{l-b}$$
is constantly equal to $\frac{1}{2\pi}$; The probability for $\delta_i\geqq\pi$ is equal to the probability that $n-1$ angles $\psi_1,\,\ldots,\,\psi_{i-1},\,\psi_{i+1},\,\ldots,\,\psi_n$ lie between $\psi_i$ and $\psi_i+\pi$, i.e. equal to $2^{-(n-1)}$. As all possibilities $\delta_i\geqq\pi$ are mutually exclusive and equally likely, this yields (c.f. $[3]$)
$$(2.24)\quad P\,(\Pi_n\ \mathrm{not}\ \mathrm{closed})=\frac{n}{2^{n-1}}$$
(if $K$ is a parallel region of $B$).
In the general case it again holds true that
$$(2.25)\quad P\,(\Pi_n\ \mathrm{not}\ \mathrm{closed})=n\int_0^{2\pi}f(\varphi)\left(\int_{\varphi}^{\varphi+\pi}f(\Theta)\,d\Theta\right)^{n-1}d\varphi\,.$$
Now obviously
$$(2.26)\quad f(\varphi)=\frac{p_1(\varphi)-p_0(\varphi)}{l-b}\geqq c\gt0$$
therefore
$$(2.27)\quad \int_{\varphi}^{\varphi+\pi}f(\Theta)\,d\Theta\leqq 1-\pi\,c$$
where
$$(2.28)\quad \pi\,c\lt\int_0^{2\pi}f(\Theta)\,d\Theta=1$$
holds true. From $(2.25) and $(2.27)$ follows
Theorem 2. If $K$ is a parallel region of $B$ then the probability that $\Pi_n$ is not closed is governed by relation $(2.24)$. If $B$ is contained in the inner of $K$, then for this probability in the general case it results in
$$(2.29)\quad P(\Pi_n\ \mathrm{not}\ \mathrm{closed})\leqq n\gamma^{n-1}$$
where $\gamma\,(0\lt\gamma\lt1)$ is a constant that depends on $B$ and $K$.
3. Random polygons around a point
Let $B=O\,\in\,K$ be a fixed point. Then $b=0$ and $l_S=2\left|\,O\,S\,\right|$ is equal to twice the length of the line segment $O\,S$. from $(2.28)$ follows
$$(3.1)\quad W_1=\frac{1}{l^2}\iint_{g_1\,\cap\,g_2\,\cap\,K\ne\emptyset}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dg_1\,dg_2$$
The condition $g_i\,\cap\,O=\emptyset$ need not be taken into consideration because the set of all through a point has measure zero. From $(2.20)$ follows, because in our case $\alpha=\pi$:
$$(3.2)\quad W_1(n)=\frac{2\pi}{l^2}\int_{S\in K}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dS\,.$$
Let $0\lt r\lt\,l/2,\ r$ fixed. Then obviously
$$(3.3)\quad \frac{2\pi}{l^2}\int_{\begin{matrix}S\in K\\ \left|\,O\,S\,\right|\gt r\end{matrix}}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dS = O(\alpha^n),\quad 0\lt\alpha \lt1,$$
where $\alpha=1-(2r)/l$ has to be set. If $K_r$ denotes the circle of radius $r$ around $O,\ K_r\subset K$, it follows that
$$(3.4)\quad W_1(n)=\frac{2\pi}{l^2}\int_{S\in K_r}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dS + O(\alpha^n)$$
with $0\lt\alpha\lt1$. For polar coordinates $\varrho,\ \Theta$ we have $dS=\varrho\,d\varrho\,d\Theta$ and by a simple calculation we get
$$(3.5)\quad E(X_n)=\frac{n(n-1)}{2}W\,(n)=\frac{\pi^2}{2}+O(\gamma^n)\quad \mathrm{with}\quad 0\lt\gamma\lt 1\,.$$
Theorem 3. The mathmatical expectation of the number $X_n$ of corners of a random convex polygon $\Pi_n$ around a point $O$ of a convex set $K$ satisfies the relation $(3.5)$.
4. Ringshaped areal around a smooth region
Concerning $B$ we now assume that the boundary curve is convex and sufficiently often continuously differentiable. Formula $(2.20)$ has to be evaluated under that precondition. In order to estimate the values $\alpha(S)$ and $l_S-b$ we first chose appropriate coordinates $t,\,s$. On the boundary $\mathscr{B}$ of $B$ we introduce the arclength $s$ as the parameter. We orient $\mathscr{B}$ counterclockwise. Let $x=f\,(s),\ y=g\,(s)$ be the equation of $\mathscr{B},\ \mathfrak{t}=\lbrace f'(s),\,g'(s)\rbrace$ the tangential vector and $\mathfrak{n}=\lbrace g',\,-f'\rbrace$ the outer normal vector; the primes denote derivation with respect to $s$. It is then $[\mathfrak{n},\,\mathfrak{t}]=1$ for the determinant of $\mathfrak{n},\,\mathfrak{t}$. The normals
$$(4.1)\quad \frac{\partial(x,\,y)}{\partial(t,\,s)}=1+t\,k(s)\gt 0\quad\mathrm{for}\quad t\gt-\frac{1}{k(s)}\,;$$
here $k(s)\,\geqq\,0$ denotes the curvature of $\mathscr{B}$ in the point $S$. For $dS$ follows
$$(4.3)\quad dS=(1+t\,k(s))\,dt\,ds\,.$$
We now consider a fixed point $Y_0$ of $\mathscr{B}$, for example $s_0=0$, and draw from an outer point $S$ on the normal through $Y_0$ the tangents to $\mathscr{B}$, which shall touch $\mathscr{B}$ in the points $Y\,(\sigma_\alpha),\ \alpha=1,\,2$ (fig. 3). For calculating approximate expressions for the values $\sigma_\alpha$ and $\tau_\alpha=\left|Y_\alpha\,S\right|$ as a function of $t$, we express the curve $\mathscr{B}$ with respect to the accompanying bipod (i.e. in its local Frenet frame) $\mathfrak{n},\ \mathfrak{t}$ in point $Y_0$:
$$\quad\quad\mathfrak{x}=\mathfrak{t}\left(s-\frac{k^2}{3!}s^3-\frac{3k\,k'}{4!}+O(s^5)\right)$$
$$(4.4)$$
$$\quad\quad-\mathfrak{n}\left(\frac{k}{2!}s^2+\frac{k'}{3!}s^3+(k''-k^3)\frac{s^4}{4!}+O(s^5)\right)\,.$$
For the intersection point $S$ of the tangent at $\mathscr{B}$ in point $Y\,(\sigma_\alpha)$ with the normal through $Y_0$ we have to evaluate the relation
$$(4.5)\quad\mathfrak{\sigma}+\tau\,\mathfrak{x}'(\sigma)'=t\mathfrak{n}$$
If we take for $\tau$ an expansion
$$(4.6)\quad\tau=A\,\sigma+B\,\sigma^2+C\,\sigma^3+D\,\sigma^4+O(\sigma^5)$$
and enter it into $(4.5)$, we get, after partitioning into the components related to $\mathfrak{t}$, $\mathfrak{n}$, two scalar equations. From the $\mathfrak{t}$-component follows
$$(4.7)\quad \tau=-\sigma-\frac{k^2}{3}\sigma^3-\frac{3}{8}k\,k'\sigma^4+O(\sigma^5)\,.$$
By comparing the coefficients of the $\mathfrak{n}$-component one gets, when taking into account $(4.7)$:
$$(4.8)\quad t=\frac{k}{2}\sigma^2+\frac{k'}{3}\sigma^3+(3k''+5\,k^3)\,\frac{\sigma^4}{4!}+O(\sigma^5)\,.$$
If we now set $t=u^2$ then an ansatz analog to $\sigma=\sigma(u)$ in $(4.8)$:
$$(4.9)\quad\sigma_{1,\,2}(u)=\pm\sqrt{\frac{2}{k}}u-\frac{2}{3}\frac{k'}{k^2}u2\pm\frac{1}{3}\sqrt{\frac{k}{2}}\left(\frac{10}{3}\frac{k'^2}{k^4}\,-\,\frac{3}{2}\frac{k''}{k^3}-\frac{5}{2}\right)u^3+O(u^4)\,.$$
That expansion makes the precondition $k\gt0$ for $\mathscr{B}$ necessary; the boundary of $B$ must not contain a line-point (Translator's Note: I guess that "Streckpunkt" means a point where the curvature vanishes) and most of all no line segment. The two signs correspond to the two tangents from $S$ to $\mathscr{B}$. Now we can evaluate the integral $(2.20)$, taking into account $(4.3)$. Accounting for the signs of the calculated lengths (fig. 3) it hold true according to $(4.7)$ that:
$$(4.10)\quad l_S-b=(\tau_2+\sigma_2)-(\tau_1-\sigma_1)=\frac{k^2}{3}(\sigma_1^3-\sigma_2^3)+\frac{3}{8}k\,k'\,(\sigma_1^4-\sigma_2^4)+O(\sigma^5)\,.$$
Because of $(4.9)$ we get
$$(4.11)\quad l_S-b=\frac{4}{3}\sqrt{2\,k}\,u^3+O(u^5)\,.$$
For $\alpha-\sin\,\alpha$ we get because of
$$(4.12)\quad\alpha(s,t)=\int_{\sigma_2}^{\sigma_1}k(\sigma)\,d\sigma$$
and taking into account $(4.9)$
$$(4.13)\quad\alpha-\sin\,\alpha=\frac{1}{3!}\left(2\sqrt{2\,k}\,u\right)^3+O(u^4)\,.$$
The integral $(2.20)$ that shall be estimated becomes, because $u=t^{1/2}$, after inserting the obtained expressions $(4.3),\ (4.11),\ (4.13)$
$$W_1(n)=\frac{2}{(l-b)^2}\int_0^b\int_0^{h(s)}\left(1-\frac{4\sqrt{2\,k}\,t^{3/2}}{3\,(l-b)}+O(t^{5/2})\right)^{n-2}\left(\frac{8}{3!}\left(\sqrt{2\,k\,t}\right)^3+O(t^2)\right)(1+tk)\,dt\,ds\,.$$
If we now substitute
$$(4.14)\quad t=\left(\frac{3\,(l-b)}{4\sqrt{2\,k}}\frac{x}{n}\right)^{2/3}$$
that yields after some rearranging
$$(4.15)\quad W_1(n)=2\left(\frac{2}{3\,(l-b)} \right)^{1/3}\int_0^bk^{2/3}\int_0^\infty\left(1-\frac{x}{n}\right)^n\frac{x^{2/3}}{n^{5/3}}\,dx\,ds+O\left(\frac{1}{n^2}\right)\,.$$
From this follows
Theorem 4. Let $B$ be a convexr finite region with smooth boundary, whose curvature $k=k(s)$ is positive and finite. $B$ be in the inner of a convex set $K$; $l$ and $b$ be the circumference of $K$, resp. $B$. For the mathematical expectation of the number of corners of a random convex polygon* $\Pi_n$ around $B$ it then holds true that
$$(4.16)\quad E(X_n)=\left[\left(\frac{2}{3\,(l-b)}\right)^{1/3}\Gamma\left(\frac{5}{3}\right)\int_0^bk^{2/3}\,ds\right]n^{1/3}+O(1)\,.$$
Consequently the order of magnitude of the number of corners is the same as in the case of the convex hull of $n$ points that are randomly chosen in $B$ (cf A.\,Rényi, R.\, Sulanke $[2]$), the factors are however significantly different.
5. Ringshaped areal around a convex polygon
Let $B$ now be a convex $r$-gon. According to theorem 1 the random polygon $\Pi_n$ lies with high probability in an arbitrary, fixed convex surrounding $U$ of $B$; $U$ shall be selected in a way that all intersection points of non-adjacent sides of $B$ are located outside of $U$. The ring-shaped areal $U\,\setminus\,B$, for which the integral $(2.20)$ must be evaluated is partitioned by the sides of $B$ into $r$ corner-regions $E_i$ and $r$ side-regions $T_i$ (fig. 4), in which we carry out the integration separately.
$T$ be one of the side-regions with corners $A,\,A'$ at a side of length $2\,c=\left|\,A\,A'\,\right|$ . For $S\in T$ it holds true that
$$(5.1)\quad l_S-b=\left|\,S\,A\,\right|+\left|\,S\,A'\,\right|-\left|\,A\,A'\,\right|=2\,(a-c)\ ,$$
where a is the semi-major axis of the ellipse with focal points $A,\ A'$ through the point $S$. As coordinates of $S$ we chose $a$ and the distance $x$ of the projection of $S$ onto the major axis of the ellipse from its center. For the area-element $dS$ we obtain in these coordinates
$$(5.2)\quad dS=\frac{a^4-c^2x^2}{a^2\sqrt{(a^2-c^2)(a^2-x^2)}}\,dx\,da\,.$$
For the angle $\alpha$ that is inserted into $(2.20)$ the outer angles of the triangle $A\,A'\,S$ in $S_i$, one calculates
$$(5.3)\quad\sin\,\alpha=\frac{2\,a\,c\sqrt{(a^2-c^2)(a^2-x^2)}}{a^4-c^2x^2}=f(x,\,a)\,.$$
We now replace the region $T$ with a section of the half-circle over $A,\,A'$ that is adjacent to $A\,A'$ and lies in $U$ and in which $\alpha\leqq\pi/2$n; we will later estimate the error that is generated by this. The is determined by $f=1$; for $x,\,a$ we get the integration-region
$$(5.4)\quad c\leqq a\leqq\delta c,\quad\left|x\right|\leqq\frac{a}{c}\sqrt{2\,c^2-a^2}\,,$$
here $\delta\ (1\lt\delta\leqq\sqrt{2})$ is a number that is chosen in a way that the circle-segment lies in $U$. According to $(2.20)$ the integral
$$(5.5)\quad W=\frac{8\,c}{(l-b)^2}\int_c^{\delta\,c}\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\left(1-\frac{2\,(a-c)}{l-b}\right)^{n-2}\left(\frac{\mathrm{arc}\sin\,f\ -\ f}{a\,f}\right)\,dx\,da$$
has to be calculated first. To that end we develop the inner integral
$$(5.6)\quad F(a) =\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\frac{1}{f}(\mathrm{arc}\sin\,f\ -\ f)\,dx$$
according to powers of $a-c$ and set
$$(5.7)\quad\frac{1}{f}(\mathrm{arc}\sin\,f\ -\ f)=\frac{1}{6}f^2+R$$
The integral over the first part yields
$$(5.8)\quad\frac{1}{6}\int_0^{(a/c)\sqrt{2\,c^2-a^2}}f^2dx=-\frac{a^4-c^4}{6\,a^2c}\log(a-c)+O(a-c)\,.$$
For the rest $R$ we show
$$(5.9)\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}R\,dx=O(a-c)\,.$$
It holds true that, if
$$\quad\mathrm{arc}\sin\,\xi=\sum_{v=0}^\infty c_v\xi^{2v+1}$$
is set,
$$(5.10)\quad 0\lt R=\sum_{v=2}^\infty c_vf^{2v}\leqq f^4\sum_{v=2}^\infty c_v=f^4\left(\frac{\pi}{2}-\frac{7}{6}\right)\,.$$
Therefore it suffices to prove
$$\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}f^4dx=(a-c)\,,$$
that is,
$$(5.11)\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\frac{(a^2-c^2)^2}{(a^4-c^2\,x^2)^4}dx=O\left(\frac{1}{a-c}\right)\,.$$
Now, because $0\leqq x\leqq c\leqq a$
$$(5.12)\quad\frac{(a-x)^2}{16\,a^2\,(a^2-c\,x)^4}\leqq\frac{(a^2-x^2)^2}{(a^4-c^2\,x^2)^4}\leqq\frac{4\,(a-x)^2}{a^6\,(a^2-c\,x)^4}\,.$$
Therefore it remains to show
$$(5.13)\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\frac{(a^2-x^2)^2}{(a^2-c\,x)^4}dx=O\left(\frac{1}{a-c}\right)$$
One easily obtains that relationeasily via the substitution $a^2-c\,x=t$ and some simple estimations. From $(5.6)-(5.9)$ we get
$$(5.14)\quad F(a)=-\frac{a^4-c^4}{6\,a^2\,c}\log\,(a-c)+O(a-c)\,.$$
According to $(5.5)$ it therefore holds true that
$$(5.15)\quad=\frac{-4}{3\,(l-b)^2}\int_0^{\delta c}\left(1-\frac{2\,(a-c)}{(l-b)}\right)^{n-2}\left(\frac{a^4-c^4}{a^3}\log\,(a-c)+O(a-c)\right)\,da\,.$$
The substitution
$$\quad\frac{2\,(a-c)}{l-b}=\frac{Z}{n-2}$$
yields after some simple calculations because of
$$(5.16)\quad\int_c^{\delta c}\left(1-\frac{2\,(a-c)}{(l-b)}\right)^{n-2}\cdot\, O(a-c)\,da=O\left(\frac{1}{n^2}\right)$$
the relation
$$(5.17)\quad W=\frac{4}{3\,n\,(n-1)}\log\,(n-2)+O\left(\frac{1}{n^2}\right)\,.$$
When replacing the side-region $T$ with a half-circle section, we have either integrated a region that is bound by the line of the neighboring side and a circular arc, too much (fig. 5 a) or too little (fig. 5 b).
We show that the errors that are generated by this are of the order of magnitude $O(1/n^2)$. Let
$$(5.18)\quad x(a)=c+(a-c)\,\gamma+O\left((a-c)^2\right)$$
be a representation of the neighboring side. The error in the first case (fig. 5 a) then is
$$(5.19)\quad\Delta=q\int_c^{\delta c}\left(1-\frac{2\,(a-c)}{(l-b)}\right)^{n-2}\frac{1}{a^2\,\sqrt{a^2-c^2}}\int_{x(a)}^{(a/c)\sqrt{2\,c^2-a^2}}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}\,dx\,da\,;$$
here $q$ denotes a constant. Because of $(5.16)$ it suffices to show that
$$(5.20)\quad I(a)=\int_{x(a)}^{(a/c)\sqrt{2\,c^2-a^2}}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}dx=O\left((a-c)^{3/2}\right)$$
holds. Now $\alpha-\sin\,\alpha$ is bound, so that it suffices to prove
$$(5.21)\quad\int_{x(a)}^{(a/c)\sqrt{2\,c^2-a^2}}\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}dx=O\left((a-c)^{3/2}\right)$$
For the indefinite integral
$$(5.22)\quad Q(x)=\int\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}dx=\frac{c^2\,x}{2}\sqrt{a^2-x^2}-a^2\,\left(a^2-\frac{c^2}{2}\right)\,\mathrm{arc}\cos\,\frac{x}{a}$$
we get, because $\mathrm{arc}\cos\frac{x}{a}=\mathrm{arc}\sin\frac{1}{a}\sqrt{a^2-x^2}$ the series expansion
$$(5.23)\quad Q(x)=\frac{1}{2}\sqrt{a^2-x^2}\,(c^2x-a^3+a(c^2-a^2)+O(a^2-x^2))\,.$$
Substituting the lower bound $x=x(a)$ according to $(5.18)$ immediately yields
$$(5.24)\quad Q(x(a))=O\left((a-c)^{3/2}\right)$$
But the same also holds for the upper bound, because the expression that is to be substituted also is of the form $(5.18)$, of course with a different constant $\gamma$. Quite analogously one also estimates the second error (fig. 5 b). Thus we may replace in $(5.17)$ the half-circle section with the side-region $T$ and alltogether get
$$(5.25)\quad W\,(T)=\frac{4}{3\,n\,(n-1)}\log\,n+O\left(\frac{1}{n^2}\right)\,.$$
This formula is also valid if $B$ degenerates to a line-segment.
Now we consider the corner-region $E=E_i$ at the corner $A_i$ of $B$. We now introduce, as in $(5.2)$, semi-elliptic coordinates; only the basis is now the line-segment $A_{i-1}\,A_{i+1}$, whose length will again be denoted by $2\,c$. With
$$\quad d=\frac{1}{2}(\left|A_{i-1}A_i\right|+\left|A_i A_{i+1}\right|)$$
we have for the difference of distance
$$(5.26)\quad l_S-b=2\,(a-d)\,.$$
Therefore, according to $(2.20)$ and $(5.2)$, for the corresponding probablity
$$(5.27)\quad W\,(E)=\frac{2}{(l-b)^2}\int_d^{a_0}\left(1-\frac{2\,(a-d)}{(l-b)}\right)^{n-2}\int_{x_1(a)}^{x_2(a)}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{a^2\sqrt{(a^2-c^2)(a^2-x^2)}}\,dx\,da\,.$$
Here $x_1(a),\ x_2(a)$ denote the $x$-coordinates of the intersection point of the ellipse that belongs to $a$ with the elongations of the sides that are adjacent to $A_i$ beyond $A_i$. As we only consider a sufficiently small surrounding of $B$, it holds true that
$$\quad\left|x\right|\leqq\max\left(\left|x_1(a)\right|,\,\left|x_1(a)\right|\right)\lt a,\quad c\lt d\leqq a\,.$$
From the mean value theorem follows, because of the boudedness and continuity of the integrand,
$$(5.28)\quad \int_{x_1(a)}^{x_2(a)}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{a^2\sqrt{(a^2-c^2)(a^2-x^2)}}dx=M(a)\,(x_2(a)-x_1(a))\,,$$
where $M(a)$ remains bounded for all $a$ from the range under consideration: $\left|\,M(a)\,\right|\leqq M_0\,.$
For $a=d$ it holds $x_1(d)=x_2(d)$. The functions $x_i(a)$ are sufficiently often differentiable in location $d$. It follows
$$(5.29)\quad x_2(a)-x_1(a)=h_0(a-d)+O\left((a-d)^2\right)\,,$$
where $h_0$ is a certain constant. If one inserts $(5.28),\ (5.29)$ into $(5.27)$, then according to $(5.16)$ follows immediately
$$(5.30)\quad W\,(E)=O\left(\frac{1}{n^2}\right)\,.$$
Because of theorem 1, $(5.25)$ and $(5.30)$ we get the following
Theorem 5. Let $B$ a convex $r$-gon, $r\geqq2$, that lies in the inner of $K$.For the mathematical expectation of the number of corners $X_n$ of a random polygon $\Pi_n$ it holds true that
$$\quad E(X_n)=\frac{2\,r}{3}\,\log n+O(1)\,.$$
The principal term of this formula matches the corresponding principal term of theorem 1of our work $[2]$ on the convex hull of random points that lie in a polygon.
References
1. Blaschke, W.: Vorlesungen über Integralgeometrie. 3. Aufl. Berlin: VEB Deutscher Verlag der Wissenschaften 1955.
2. Rényi, A., u. R. Sulanke: Über die konvexe Hülle von $n$ zufällig gewählten Punkten. Z. Wahrscheinlichkeitstheorie verw. Geb. 2, 75-84 (1963).
3. Stevens, W.L.: Solution to a geometrical problem in probability. Ann. Eugenics 9, 315-320 (1939.
Dr. R. Sulanke
Mathematisches Institut der
Humboldt-Universität
Berlin
Prof. Dr. A. Rényi
Mathematisches Institut der Ungarischen
Akademie der Wissenschaften
Reáltonada u. 13-15
Budapest V, Ungarn
No comments:
Post a Comment