TY - GEN
T1 - FPTAS for minimizing earth mover's distance under rigid transformations
AU - Ding, Hu
AU - Xu, Jinhui
PY - 2013
Y1 - 2013
N2 - In this paper, we consider the problem (denoted as EMDRT) of minimizing the earth mover's distance between two sets of weighted points A and B in a fixed dimensional ℝd space under rigid transformation. EMDRT is an important problem in both theory and applications and has received considerable attentions in recent years. In this paper, we present the first FPTAS algorithm for EMDRT. Our algorithm runs roughly in O((nm)d+2 (lognm) 2d) time which matches the order of magnitude of the degree of a lower bound for any PTAS of this problem, where n and m are the sizes of A and B, respectively. Our result is based on several new techniques, such as the Sequential Orthogonal Decomposition (SOD) and Optimum Guided Base (OGB). Our technique can also be extended to several related problems, such as the alignment problem, and achieves FPTAS for each of them.
AB - In this paper, we consider the problem (denoted as EMDRT) of minimizing the earth mover's distance between two sets of weighted points A and B in a fixed dimensional ℝd space under rigid transformation. EMDRT is an important problem in both theory and applications and has received considerable attentions in recent years. In this paper, we present the first FPTAS algorithm for EMDRT. Our algorithm runs roughly in O((nm)d+2 (lognm) 2d) time which matches the order of magnitude of the degree of a lower bound for any PTAS of this problem, where n and m are the sizes of A and B, respectively. Our result is based on several new techniques, such as the Sequential Orthogonal Decomposition (SOD) and Optimum Guided Base (OGB). Our technique can also be extended to several related problems, such as the alignment problem, and achieves FPTAS for each of them.
UR - https://www.scopus.com/pages/publications/84884320624
U2 - 10.1007/978-3-642-40450-4_34
DO - 10.1007/978-3-642-40450-4_34
M3 - Conference contribution
SN - 9783642404498
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 397
EP - 408
BT - Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings
T2 - 21st Annual European Symposium on Algorithms, ESA 2013
Y2 - 2 September 2013 through 4 September 2013
ER -