论文标题
空间中随机点的chirotopes在小整数网格上可以实现
Chirotopes of Random Points in Space are Realizable on a Small Integer Grid
论文作者
论文摘要
我们证明，有了很高的概率，可以将$ n $点的均匀样本在$ \ mathbb {r}^d $中的凸形域中的均匀样本舍入到点上的圆形，该网格的步骤大小与$ 1/n^{d+1+1+ε} $成比例的网格，而无需更改基础chirotope（方向的仿真）。因此，可以用$ O（n \ log n）$位编码随机点集的chirotopes。这与最坏的情况形成了鲜明的对比，在这种情况下，即使对于$ d = 2 $，网格可能被迫具有$ 1/2^{2^{ω（n）}} $的步长$ 1/2^{2^{ω（n）}} $。 该结果是由于Fabila-Monroy和Huemer（2017）和Devillers，Duchon，Glisse和Goaoc（2018），对先前的结果进行了对先前结果的高度概括。
We prove that with high probability, a uniform sample of $n$ points in a convex domain in $\mathbb{R}^d$ can be rounded to points on a grid of step size proportional to $1/n^{d+1+ε}$ without changing the underlying chirotope (oriented matroid). Therefore, chirotopes of random point sets can be encoded with $O(n\log n)$ bits. This is in stark contrast to the worst case, where the grid may be forced to have step size $1/2^{2^{Ω(n)}}$ even for $d=2$. This result is a high-dimensional generalization of previous results on order types of random planar point sets due to Fabila-Monroy and Huemer (2017) and Devillers, Duchon, Glisse, and Goaoc (2018).
