论文标题
高维一致的数字射线和2D部分一致的数字光线的距离界限
Distance bounds for high dimensional consistent digital rays and 2-D partially-consistent digital rays
论文作者
论文摘要
我们考虑了数字化欧几里得细分市场的问题。具体来说，我们寻找一种建设性方法，可以在$ \ mathbb {z}^d $中连接任意两个点。构造必须是{\ em一致}（即满足欧几里得公理的自然延伸），同时尽可能地类似于它们。以前的工作显示了$θ（\ log n）$错误的两个维度的渐近紧密结果，其中段之间的相似之处是使用Hausdorff距离测量，而$ n $是两个点之间的$ L_1 $距离。由于适用于$ \ Mathbb {z}^2 $的任何一致结构的$ω（\ log n）$下限，因此被认为是紧密的。 在本文中，我们观察到下限并未直接扩展到更高的维度。我们提供了一个替代参数，表明$ d $ dimensions中的任何一致的结构都必须具有$ω（\ log^{1/（d-1）} n）$错误。我们将一致构造的误差与高维的一致结构联系在一起，以在两个维度中的相似{\ em弱}构造的误差（某些点不需要所有公理的构造）。这不仅打开了具有$ O（\ log n）$在高维度上的构造的可能性，而且还为公理违规数量和构造错误之间的权衡开辟了有趣的研究。为了显示我们的下限，我们还考虑了我们发现独立兴趣的一组点差异概念的彩色变化。
We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in $\mathbb{Z}^d$. The construction must be {\em consistent} (that is, satisfy the natural extension of the Euclidean axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with $Θ(\log N)$ error, where resemblance between segments is measured with the Hausdorff distance, and $N$ is the $L_1$ distance between the two points. This construction was considered tight because of a $Ω(\log N)$ lower bound that applies to any consistent construction in $\mathbb{Z}^2$. In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in $d$ dimensions must have $Ω(\log^{1/(d-1)} N)$ error. We tie the error of a consistent construction in high dimensions to the error of similar {\em weak} constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with $o(\log N)$ error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. In order to show our lower bound, we also consider a colored variation of the concept of discrepancy of a set of points that we find of independent interest.
