×

Partial-matching RMS distance under translation: combinatorics and algorithms. (English) Zbl 1392.68424

Summary: We consider the problem of minimizing the RMS distance (sum of squared distances between pairs of points) under translation between two point sets \(A\) and \(B\), in the plane, with \(m=|B|\ll n=|A|\), in the partial-matching setup, in which each point in \(B\) is matched to a distinct point in \(A\). Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision \({\mathcal {D}}_{B,A}\) of the plane and derive improved bounds on its complexity. Specifically, we show that this complexity is \(O(n^2m^{3.5} (e \ln m+e)^m)\), so it is only quadratic in \(|A|\). These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abdulkadiroğlu, A; Sönmez, T, Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 3, 689-701, (1998) · Zbl 1019.91016 · doi:10.2307/2998580
[2] Agarwal, P.K., Phillips, J.M.: On bipartite matching under the RMS distance. In: Proceedings of 18th Canadian Conference on Computational Geometry (CCCG’06), pp. 143-146 (2006)
[3] Asinowski, A., Keszegh, B., Miltzow, T.: Counting houses of pareto optimal matchings in the house allocation problem. In: Ferro, A., Luccio, F., Widmayer, P. (eds.) Fun with Algorithms. Lecture Notes in Computer Science, vol. 8496, pp. 301-312. Springer, Sicily, Italy (2014) · Zbl 1401.91453
[4] Balogh, J; Regev, O; Smyth, C; Steiger, W; Szegedy, M, Long monotone paths in line arrangements, Discrete Comput. Geom., 32, 167-176, (2003) · Zbl 1065.52016
[5] Ben-Avraham, R., Henze, M., Jaume, R., Keszegh, B., Raz, O.E., Sharir, M., Tubis, I.: Minimum partial matching and Hausdorff RMS-distance under translation: combinatorics and algorithms. In: Proceedings of 22nd European Symposium on Algorithms, pp. 100-111 (2014) · Zbl 1423.68538
[6] Clarkson, KL; Shor, PW, Applications of random sampling in computational geometry, II, Discrete Comput. Geom., 4, 387-421, (1989) · Zbl 0681.68060 · doi:10.1007/BF02187740
[7] de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry, Algorithms and Applications. Springer, Berlin (1997); second edition (2000) · Zbl 0939.68134
[8] Dumitrescu, A; Rote, G; Tóth, CD; Bezdek, K (ed.); Deza, A (ed.); Ye, Y (ed.), Monotone paths in planar convex subdivisions and polytopes, No. 69, 79-104, (2013), Berlin · Zbl 1275.52019 · doi:10.1007/978-3-319-00200-2_6
[9] Edmonds, J; Karp, RM, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19, 248-264, (1972) · Zbl 0318.90024 · doi:10.1145/321694.321699
[10] Fredman, ML; Tarjan, RE, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, 34, 596-615, (1987) · doi:10.1145/28869.28874
[11] Henze, M., Jaume, R., Keszegh, B.: On the complexity of the partial least-squares matching Voronoi diagram. In: Proceedings of 29th European Workshop on Computational Geometry (EuroCG’13) (2013) · Zbl 0318.90024
[12] Jung, I., Lacroix, S.: A robust interest points matching algorithm. In: Proceedings of ICCV’01, vol. 2, pp. 538-543 (2001)
[13] Kuhn, HW, The Hungarian method for the assignment problem, Naval Res. Logist. Q., 2, 83-97, (1955) · Zbl 0143.41905 · doi:10.1002/nav.3800020109
[14] Ramshaw, L., Tarjan, R.E.: A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs. In: Proceedings of 53rd Annual IEEE Symposium on Foundations of Computer Science, pp. 581-590 (2012) · Zbl 0681.68060
[15] Rote, G.: Partial least-squares point matching under translations. In: Proceedings of 26th European Workshop on Computational Geometry (EuroCG’10), pp. 249-251 (2010)
[16] Rote, G.: Long monotone paths in convex subdivisions. In: Proceedings of 27th European Workshop on Computational Geometry (EuroCG’11), pp. 183-184 (2011) · Zbl 1065.52016
[17] Shapley, LS; Scarf, H, On cores and indivisibility, J. Math. Econ., 1, 23-37, (1974) · Zbl 0281.90014 · doi:10.1016/0304-4068(74)90033-0
[18] Umeyama, S, Least-squares estimation of transformation parameters between two point patterns, IEEE Trans. Pattern Anal. Mach. Intell., 13, 376-380, (1991) · doi:10.1109/34.88573
[19] Zikan, K; Silberberg, TM; Shapiro, L (ed.); Rosenfeld, A (ed.), The Frobenius metric in image registration, 385-420, (1992), Amsterdam
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.