{"ID":6536192,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10703","arxiv_id":"2607.10703","title":"Rectilinear Matching to the Integer Grid in Nearly-Linear Time","abstract":"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 difficulty is that the target set is infinite: one must first identify a finite set of relevant grid points without losing optimality. We prove a geometric compression theorem for this infinite-target problem. In $O(n\\log^2 n)$ time, we construct a set $\\mathcal{C}$ of asymptotically optimal size $O(n)$ such that, simultaneously for every $p\\in[1,\\infty]$, some optimal $\\ell_p$ assignment uses only points of $\\mathcal{C}$. The construction is independent of the subsequent optimization algorithm and of the coordinate spread. For the rectilinear case, we combine this candidate set with a linear-size sparse network representation of $\\ell_1$ distances. In the word-RAM model with $O(1)$-word dyadic coordinates and $O(\\log n)$ fractional bits, a nearly-linear time minimum-cost flow algorithm then gives a randomized exact algorithm with expected running time $\\widetilde O(n)$. This improves the standard $\\widetilde O(n^2)$ approach. Combined with existing finite geometric matching algorithms, the same candidate set also gives an $\\widetilde O(n\\sqrt n\\log(1/\\varepsilon))$-time $(1+\\varepsilon)$ approximation for every fixed integer $p\\ge1$.","short_abstract":"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 difficulty is that the target set is infinite: one must first identify a finite set of relevant grid points without losing optimality. We prove a...","url_abs":"https://arxiv.org/abs/2607.10703","url_pdf":"https://arxiv.org/pdf/2607.10703v1","authors":"[\"Yu Gao\"]","published":"2026-07-12T10:54:54Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DS\"]","methods":"[]","has_code":false}