论文标题
仿射不变的三角形
Affine invariant triangulations
论文作者
论文摘要
我们研究仿射不变的2D三角测量方法。也就是说，对于任何（未知）$ s $的仿射转换，生成相同的三角剖分的方法。我们的工作是基于Nielson的方法[仿射不变三角剖分的特征。地理。 mod，191-210。 Springer，1993年]使用$ s $的协方差矩阵倒数来定义仿射不变的规范，表示$ a_ {s} $和一个仿射不变的三角剖分，表示为$ {dt} _ {a_ {a_ {s}}}} [s] $。从几何角度来看，我们重新访问$ a_ {s} $ - 标准，并证明$ {dt} _ {a_ {s}} [s] $可以看作是基于$ s $的转换点集的标准delaunay三角剖分。我们证明它保留了其所有众所周知的属性，例如1-tough，包含完美的匹配，并且是$ s $的完整几何图的持续扳手。我们表明，$ a_ {s} $ - norm扩展到相关几何结构的层次结构，例如最小跨越树，最近的邻居图，Gabriel图，相对邻域图和这些图形的高阶版本。此外，我们还提供了点集$ s $的不同仿射不变分类方法以及可以与已知算法结合的多边形$ p $的顶点，以获取其他仿射不变的三角测量方法，$ s $和$ p $。
We study affine invariant 2D triangulation methods. That is, methods that produce the same triangulation for a point set $S$ for any (unknown) affine transformation of $S$. Our work is based on a method by Nielson [A characterization of an affine invariant triangulation. Geom. Mod, 191-210. Springer, 1993] that uses the inverse of the covariance matrix of $S$ to define an affine invariant norm, denoted $A_{S}$, and an affine invariant triangulation, denoted ${DT}_{A_{S}}[S]$. We revisit the $A_{S}$-norm from a geometric perspective, and show that ${DT}_{A_{S}}[S]$ can be seen as a standard Delaunay triangulation of a transformed point set based on $S$. We prove that it retains all of its well-known properties such as being 1-tough, containing a perfect matching, and being a constant spanner of the complete geometric graph of $S$. We show that the $A_{S}$-norm extends to a hierarchy of related geometric structures such as the minimum spanning tree, nearest neighbor graph, Gabriel graph, relative neighborhood graph, and higher order versions of these graphs. In addition, we provide different affine invariant sorting methods of a point set $S$ and of the vertices of a polygon $P$ that can be combined with known algorithms to obtain other affine invariant triangulation methods of $S$ and of $P$.
