Jul 23, 2016
I will survey algorithms for testing whether two point sets are congruent, that is, equal up to a Euclidean isometry. I will introduce the important techniques for congruence testing, namely dimension reduction and pruning, or more generally, condensation. I will illustrate these techniques on the three-dimensional version of the problem. I will then discuss algorithms for higher dimensions, and in particular, highlight the unpublished contributions of Jiří Matoušek. Finally, I will sketch our recent algorithm for four dimensions with near-linear running time (joint work with Heuna Kim).
International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016
Professional recording and live streaming, delivered globally.
Presentations on similar topic, category or speaker