On the Expected Complexity of Random Convex Hulls
On the Expected Complexity of Random Convex Hulls
复制标题
关于随机凸壳的预期复杂度
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Sariel Har
中科院分区：
文献类型：
--
作者：
Sariel Har
在本文中，我们提供了几个结果，内容涉及均匀和独立于凸形的凸壳的预期复杂性。
（i）我们表明，从磁盘上独立和独立选择的凸壳的预期顶点数为$ O（n^{1/3}）$和$ o（k log {n }）$对于带有$ k $侧的凸多边形。这些结果是众所周知的（请参阅cite {rs-udkhv-63，r-slcdn-70，ps-cgi-85}），但我们相信这里给出的基本证明更简单，更直观。
（ii）让$ d $是飞机上的一组指示，我们定义了$ d $引起的凸的广义概念，该概念既扩展了直线性凸度和标准凸度。
我们证明，一组$ n $点的$ d $ -convex船体的预期复杂性均匀地和独立于磁盘选择，为$ o（n^{1/3} + sqrt {nalpha（d）} ）$，其中$ alpha（d）$是$ d $中两个连续两个向量之间的最大角度。该结果扩展了直线和标准凸度病例的已知边界。
（iii）让$ b $是$ re^d $中的轴平行的hypercube。我们证明，$ n $ n $点的象限船体边界上的预期点数均匀地从$ b $中独立选择为$ o（log^{d-1} n）$。一组点的象限船体是直线凸的扩展到更高尺寸的。特别是，此数字大于$ s $中的最大值数量，并且也大于$ s $的点的点数，这些点是$ s $的凸壳的顶点。
这些界限是已知的{BKST-ANMSV-78}，但我们认为新的证明更简单。
In this paper we present several results on the expected complexity of a convex hull of $n$ points chosen uniformly and independently from a convex shape.
(i) We show that the expected number of vertices of the convex hull of $n$ points, chosen uniformly and independently from a disk is $O(n^{1/3})$, and $O(k log{n})$ for the case a convex polygon with $k$ sides. Those results are well known (see cite{rs-udkhv-63,r-slcdn-70,ps-cgi-85}), but we believe that the elementary proof given here are simpler and more intuitive.
(ii) Let $D$ be a set of directions in the plane, we define a generalized notion of convexity induced by $D$, which extends both rectilinear convexity and standard convexity.
We prove that the expected complexity of the $D$-convex hull of a set of $n$ points, chosen uniformly and independently from a disk, is $O(n^{1/3} + sqrt{nalpha(D)})$, where $alpha(D)$ is the largest angle between two consecutive vectors in $D$. This result extends the known bounds for the cases of rectilinear and standard convexity.
(iii) Let $B$ be an axis parallel hypercube in $Re^d$. We prove that the expected number of points on the boundary of the quadrant hull of a set $S$ of $n$ points, chosen uniformly and independently from $B$ is $O(log^{d-1}n)$. Quadrant hull of a set of points is an extension of rectilinear convexity to higher dimensions. In particular, this number is larger than the number of maxima in $S$, and is also larger than the number of points of $S$ that are vertices of the convex hull of $S$.
Those bounds are known cite{bkst-anmsv-78}, but we believe the new proof is simpler.