Rectilinear Matching to the Integer Grid in Nearly-Linear Time

Yu Gao

Rectilinear matching to the integer grid asks to assign each of $n$ points in ${\mathbb{R}}^2$ to a distinct point of ${\mathbb{Z}}^2$, minimizing total ${\ell }_1$ movement. The main diffi…