Matching points between 2 polygons

Given 2 polygons in a plane:

$A : ( (xa_1,ya_1), (xa_2,ya_2), ... (xa_n,ya_n) )$

$B : ( (xb_1,yb_1), (xb_2,yb_2), ... (xb_m,yb_m) )$

Is there a polynomial algorithm to compute a matching $M$ between the points in A and B, such that:

• If $(xa_i,ya_i)$ is matched to $(xb_p,yb_p)$ and $(xa_k,ya_k)$ is matched to $(xb_r,yb_r)$, then for $i

• For $M:\{(i_1,j_1),(i_2,j_2)...\}$ and $|M|=min(n,m)$, $\Sigma_{k=1}^{|M|} distance((xa_{i_k},ya_{i_k}),(xb_{j_k},yb_{j_k}))$ is minimized.

This is a large topic, often called "geometric shape matching." Here is one survey that can lead to many specific algorithms:


H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 121–153. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000. doi:10.1016/B978-044482537-7/50004-8

If you have difficulty accessing that chapter, an earlier draft of the survey
is here: PDF download.

StackExchange Computer Science Q#75686, answer score: 3