论文标题
随机订单类型的凸壳
Convex Hulls of Random Order Types
论文作者
论文摘要
我们建立了以下两个主要结果，该结果是飞机中一般位置的积分的订单类型（可实现的简单平面订单类型，可实现的均匀无环为方面的等级级别$ 3 $）： （a）从所有此类订单类型中随机选择的$ n $点订单类型中的极端点数量平均为$ 4+o（1）$。对于标记的订单类型，此数字的平均$ 4- \ frac {8} {n^2 -n +2} $和最多3 $的差异。 （b）（标记的）订单类型读取一组$ n $点，独立于凸面平面域，平滑或多边形的均匀度量，或从高斯分布中读取，即集中使用，即，这种采样通常仅遇到给定尺寸的所有订单类型的小部分。 结果（a）将标记的订单类型类型的任意维度$ d $概括为$ 2D+o（1）$和恒定差异。我们还讨论了我们的方法在多大程度上推广到均匀无环的矩形的抽象设置。此外，我们的方法允许显示Erdős-Szekeres定理的以下亲戚：对于任何固定的$ k $，如$ n \ to \ infty $，$ 1- o（1/n）$（1/n）的比例简单订单类型包含一个三角形的三角形封闭凸$ k $的三角形。 对于（a）中的未标记案例，我们证明，对于$ 2 $维二维球的任何反物，有限的子集，保持方向保留双线的组是环状的，二二的，或$ A_4 $，$ S_4 $或$ s_4 $或$ a_5 $的一组。这些是$（3）$的有限子组，我们的证明遵循Felix Klein的表征。
We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented matroids of rank $3$): (a) The number of extreme points in an $n$-point order type, chosen uniformly at random from all such order types, is on average $4+o(1)$. For labeled order types, this number has average $4- \frac{8}{n^2 - n +2}$ and variance at most $3$. (b) The (labeled) order types read off a set of $n$ points sampled independently from the uniform measure on a convex planar domain, smooth or polygonal, or from a Gaussian distribution are concentrated, i.e. such sampling typically encounters only a vanishingly small fraction of all order types of the given size. Result (a) generalizes to arbitrary dimension $d$ for labeled order types with the average number of extreme points $2d+o(1)$ and constant variance. We also discuss to what extent our methods generalize to the abstract setting of uniform acyclic oriented matroids. Moreover, our methods allow to show the following relative of the Erdős-Szekeres theorem: for any fixed $k$, as $n \to \infty$, a proportion $1 - O(1/n)$ of the $n$-point simple order types contain a triangle enclosing a convex $k$-chain over an edge. For the unlabeled case in (a), we prove that for any antipodal, finite subset of the $2$-dimensional sphere, the group of orientation preserving bijections is cyclic, dihedral or one of $A_4$, $S_4$ or $A_5$ (and each case is possible). These are the finite subgroups of $SO(3)$ and our proof follows the lines of their characterization by Felix Klein.
