An FPTAS for an Elastic Shape Matching Problem with Cyclic Neighborhoods
An FPTAS for an Elastic Shape Matching Problem with Cyclic Neighborhoods
复制标题
循环邻域弹性形状匹配问题的 FPTAS
DOI：
10.1007/978-3-319-95165-2_30
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Fabian Stehn
中科院分区：
文献类型：
--
作者：
Christian Knauer;Luise Sommer;Fabian Stehn
在计算几何中，弹性几何形状匹配（EGSM）问题类是众所周知的几何形状匹配问题类的推广：给定两个几何形状，“图案”和"模型“，从给定的变换类中找到一个单一的变换，如果将其应用于图案，则最小化变换后的图案和模型之间的距离。在EGSM中，该图案被划分为通过“变换集合”变换的子形状，即，一组变换。目标是最小化变换子模式的并集与对象空间中的模型之间的距离，以及集合的特定变换之间的距离。“邻居图”对哪些平移应该相似进行编码。我们针对具有固定对应关系的平移下的点序列的EGSM实例提出了一种完全多项式时间逼近方案（FPTAS），其中邻居图是一个简单的循环。
In computational geometry, the elastic geometric shape matching (EGSM) problem class is a generalisation of the well-known geometric shape matching problem class: Given two geometric shapes, the ‘pattern’ and the ‘model’, find asingletransformation from a given transformation class that, if applied to the pattern, minimizes the distance between the transformed pattern and the model with respect to a suitable distance measure.In EGSM, the pattern is divided into subshapes that are transformed by a ‘transformation ensemble’, i.e., a set of transformations. The goal is to minimize the distance between the union of the transformed subpatterns and the model in object space as well as the distance between specific transformations of the ensemble. The ‘neighborhood graph’ encodes which translations should be similar.We present a fully polynomial time approximation scheme (FPTAS) for EGSM instances for point sequences under translations with fixed correspondence where the neighborhood graph is a simple cycle.
DOI：
10.1016/j.comgeo.2018.01.002
发表时间：
2018-08
期刊：
Comput. Geom.
影响因子：
--
作者：
Christian Knauer;Luise Sommer;Fabian Stehn
通讯作者：
Christian Knauer;Luise Sommer;Fabian Stehn