FPTAS for Minimizing the Earth Mover’s Distance Under Rigid Transformations and Related Problems
FPTAS for Minimizing the Earth Mover’s Distance Under Rigid Transformations and Related Problems
复制标题
DOI：
10.1007/s00453-016-0173-4
复制
发表时间：
2017-07
期刊：
影响因子：
1.1
通讯作者：
Hu Ding;Jinhui Xu
中科院分区：
文献类型：
--
作者：
Hu Ding;Jinhui Xu
本文研究了刚体变换下最小化推土机在两组权点A和B之间的距离的问题（记作EMDRT）。EMDRT是一个重要的理论和应用问题，近年来受到了广泛的关注。以往对该问题的研究仅限于常数因子近似，而PTAS的求解一直是一个悬而未决的问题。在本文中，我们提出了第一个EMDRT的FPTAS算法。我们的算法运行大致在时间上（这是接近任何PTAS对这个问题的下限），其中和分别是A和B的大小。我们的结果是基于几个新的技术，如顺序正交分解和最优引导基，并可以扩展到几个相关的问题，如推土机的相似变换下的距离问题和对齐问题，以实现对每一个他们的FPTAS。
In this paper, we consider the problem (denoted as EMDRT) of minimizing the earth mover’s distance between two sets of weighted pointsAandBinunder rigid transformation. EMDRT is an important problem in both theory and applications and has received considerable attentions in recent years. Previous research on this problem has resulted in only constant factor approximations and it has been an open problem for a long time to achieve PTAS solution. In this paper, we present the first FPTAS algorithm for EMDRT. Our algorithm runs roughly intime (which is close to a lower bound on any PTAS for this problem), wherenandmare the sizes ofAandB, respectively. Our result is based on several new techniques, such as theSequential Orthogonal DecompositionandOptimum Guided Base, and can be extended to several related problems, such as the problem of earth mover’s distance under similarity transformation and the alignment problem, to achieve FPTAS for each of them.