# 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

## 1 Answer

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.