# 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:

1. 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<j<k$ and $p<q<r$, $(xa_j,ya_j)$ is matched to $(xb_q,yb_q)$.
2. 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.
• You define two polygons, but match polylines. It seems to me that your polylines should be allowed to go around polygons, like in cyclical order. Can you please clarify that? – HEKTO May 20 '17 at 16:11
• Yes, i want to describe it like that but can not find the exact wording. But either one is okay for my application actually. – axeven May 21 '17 at 19:23