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 R~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)(log nm)~(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.
展开▼
