论文标题
2D中弱一致的数字光线的最佳界限
Optimal Bounds for Weak Consistent Digital Rays in 2D
论文作者
论文摘要
数字空间中欧几里得对象的代表已有30多年的重点。数字线段段尤其重要，因为其他数字对象取决于其定义（例如，数字凸对象或数字星形对象）。数字线段系统可能需要满足其欧几里得同行所满足的一些不错的属性。该系统是一个一致的数字线段系统（CD），如果它满足五个属性，则最著名的是子细分属性（任何两个数字线段的交集都应连接）并延长属性（任何数字线段都应能够扩展到数字线路）。众所周知，任何CD都必须具有$ω（\ log n）$ hausdorff距离其欧几里得对应物的距离，其中$ n $是一个细分市场上的网格点数。实际上，这种下限甚至适用于一致的数字射线（CDR），其中固定的$ p \ in \ mathbb {z}^2 $，我们考虑了数字段从$ p $到$ q $的数字段，每个$ q \ in \ in \ mathbb {z}^2 $。在本文中，我们考虑了弱一致的数字射线（WCDR）的家庭，在该家族中，我们维护了四个CDR属性，但排除了延长属性。在本文中，我们给出了一个WCDR结构，该结构具有最佳的Hausdorff距离至确切的常数。也就是说，我们给出了一个结构，其Hausdorff距离为$ L_ \ infty $ Metric，我们的Hausdorff距离为1.5，并且我们证明，对于每$ε> 0 $，就不可能拥有带有Hausdorff距离的WCDR，最多是$1.5-ε$。
Representation of Euclidean objects in a digital space has been a focus of research for over 30 years. Digital line segments are particularly important as other digital objects depend on their definition (e.g., digital convex objects or digital star-shaped objects). It may be desirable for the digital line segment systems to satisfy some nice properties that their Euclidean counterparts also satisfy. The system is a consistent digital line segment system (CDS) if it satisfies five properties, most notably the subsegment property (the intersection of any two digital line segments should be connected) and the prolongation property (any digital line segment should be able to be extended into a digital line). It is known that any CDS must have $Ω(\log n)$ Hausdorff distance to their Euclidean counterparts, where $n$ is the number of grid points on a segment. In fact this lower bound even applies to consistent digital rays (CDR) where for a fixed $p \in \mathbb{Z}^2$, we consider the digital segments from $p$ to $q$ for each $q \in \mathbb{Z}^2$. In this paper, we consider families of weak consistent digital rays (WCDR) where we maintain four of the CDR properties but exclude the prolongation property. In this paper, we give a WCDR construction that has optimal Hausdorff distance to the exact constant. That is, we give a construction whose Hausdorff distance is 1.5 under the $L_\infty$ metric, and we show that for every $ε> 0$, it is not possible to have a WCDR with Hausdorff distance at most $1.5 - ε$.
