Pith. sign in

REVIEW 5 minor 12 references

A linear set of grid points captures an optimal assignment for every ℓp norm, unlocking nearly-linear exact rectilinear matching.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-14 09:52 UTC pith:5JMNL34I

load-bearing objection Solid geometric compression to a linear candidate set for infinite-grid matching, with a clean nearly-linear exact ℓ1 algorithm that rests on a standard black-box flow solver.

arxiv 2607.10703 v1 pith:5JMNL34I submitted 2026-07-12 cs.CG cs.DS

Rectilinear Matching to the Integer Grid in Nearly-Linear Time

Yu Gao This is my paper
classification cs.CG cs.DS MSC 68U0568Q2590C2705C85
keywords rectilinear matchinginteger gridcandidate setsafe pruningminimum-cost flowgeometric bipartite matchingℓp normslegalization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the problem of sending n points in the plane to distinct integer lattice sites while minimizing total rectilinear movement. The target lattice is infinite, so any algorithm must first shrink the relevant sites without discarding an optimal solution. The authors prove that a single, explicitly built set of O(n) lattice points already contains the targets of an optimal assignment for every ℓp norm at once, and that this set can be constructed in O(n log² n) time by iterated safe pruning of displacement radii. For the rectilinear case they further encode the distances on a linear-size sparse network that is separable, so a black-box nearly-linear min-cost-flow solver yields a randomized exact algorithm of expected Õ(n) time under standard word-RAM assumptions on the coordinates. The same candidate set also feeds existing finite geometric matching algorithms to give a fast approximation for every fixed integer p. The result removes the quadratic candidate blow-up that had blocked subquadratic exact methods.

Core claim

There exists an algorithm that, in O(n log² n) time, builds a set C of O(n) lattice points such that, for every p in [1,∞], some optimal ℓp assignment of the n inputs uses only points of C; for the ℓ₁ norm this set plus a linear-size separable flow network yields a randomized exact algorithm of expected Õ(n) time.

What carries the argument

The universal optimal-size candidate set produced by iterated safe pruning: a p-independent sequence of geometrically shrinking test radii, each applied via a square-covering overcount of potential supporters, yields a final safe radius vector whose ℓ∞ squares contain only O(n) lattice points while still housing an optimal assignment for every norm.

Load-bearing premise

The claimed nearly-linear running time for exact rectilinear matching rests on a black-box nearly-linear min-cost-flow algorithm for separable graphs with polynomially bounded integer costs; if that solver does not deliver its guarantee on the constructed network, the Õ(n) bound fails even though the candidate set remains valid.

What would settle it

Construct a concrete n-point instance whose optimal ℓ₁ assignment uses a lattice point outside the O(n)-size candidate set returned by the iterated-pruning procedure, or show that the sparse flow network built from that set has cost strictly larger than the true optimum.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies Min-cost Grid Matching: assign n (possibly coincident) points in R^{2} injectively to Z^{2} minimizing total ℓ_p cost. The core contribution is a p-independent geometric compression (Theorem 1.2): in O(n log^{2} n) time one constructs an O(n)-size candidate set C ⊆ Z^{2} that contains the image of some optimal assignment simultaneously for every p ∈ [1, ∞]. For the rectilinear (ℓ₁) case the candidates are combined with a linear-size sparse rectilinear network (Theorem 1.6) whose optimum equals the matching cost and whose underlying undirected graph is 1/2-separable; invoking the nearly-linear separable min-cost-flow algorithm of Dong et al. then yields a randomized exact algorithm of expected Õ(n) time under a word-RAM model with O(1)-word dyadic coordinates (Theorem 1.4). The same candidate set immediately supplies an Õ(n√n log(1/ε))-time (1+ε)-approximation for every fixed integer p ≥ 1. Appendices treat two common target-restricted variants and an alternative range-tree flow reduction.

Significance. If correct, the result removes the quadratic candidate-set bottleneck that previously forced Õ(n^{2}) exact algorithms for unrestricted infinite-grid matching, and supplies a nearly-linear exact algorithm that is optimal up to polylog factors. The candidate-set theorem is of independent interest: it is asymptotically tight, works uniformly for all ℓ_p, is independent of coordinate spread, and can be used as a black-box front-end for any finite geometric matching algorithm. The geometric arguments (safe radii, square-covering estimator, iterated pruning with high-radius charging) are elementary and self-contained; the only external engine is a standard separable MCF solver applied after an explicit linear-size reduction. Applications in VLSI legalization and grid-map visualization make the algorithmic improvement practically relevant as well.

minor comments (5)
  1. In the proof of Lemma 5.5 the constant b = 12 is fixed without comment; a short sentence explaining that any b ≥ 8 works (from the distance calculation 4R_{t-1} = 8R_t) would make the choice transparent.
  2. Section 6, network construction: the claim that “all noncollinear intersections occur at endpoints” is correct for the described segments, but a one-line justification (horizontal source-to-anchor segments meet vertical anchor-to-grid segments only at anchors) would help a reader verify planarity/separability quickly.
  3. Appendix B (coordinate normalization): the constant K > 6 is used to guarantee that components of diameter O(n) remain separated by more than the initial safe radius; stating the concrete inequality 3√n < (K n)/2 would make the argument fully self-contained.
  4. Typographical: several places write “eO” or “ẽO” in the text body (e.g., abstract, Theorem 1.4 statement); consistent use of the already-defined Õ notation would improve readability.
  5. Related-work paragraph on finite geometric matching: the citation to Sharathkumar–Agarwal [SA12] is for diameter-Δ instances; a parenthetical note that the present candidate set removes the Δ dependence would clarify the improvement.

Circularity Check

0 steps flagged

No significant circularity: candidate-set construction and ℓ1 reduction are self-contained geometric arguments; co-authored MCF solver is used only as a black-box runtime engine.

full rationale

The load-bearing derivation is Theorem 1.2 (universal O(n) candidate set via iterated safe pruning). It proceeds from an initial safe radius (Lemma 3.1, uniform over p by grid-point counting in balls), the square-covering estimator (Lemma 3.2–3.5), simultaneous pruning (Lemma 3.4), and a charging argument that bounds the high-radius region U(2)T by O(n) via freshness/disjointness of the Xt sets and coverage of St (Lemmas 5.3–5.8). All steps are proved from first principles with packing and area comparisons; no quantity is defined in terms of the final optimum or fitted to data. The ℓ1 flow network (Theorem 1.6) equates matching cost to MCF value by explicit path decomposition and integral-flow recovery; separability follows from planarity after deleting the sink. The only external citation used for the ẽO(n) claim is the separable MCF algorithm of Dong et al. [DGG+25] (co-authored by the present author). It is invoked strictly as a black-box runtime engine under polynomially-bounded integral costs after scaling by 2B, after the paper has already proved that the constructed network has the same optimum value and belongs to a 1/2-separable family. This does not make the geometric claims circular, nor does it redefine the matching optimum. No fitted parameters, uniqueness theorems, or ansatzes are smuggled in; the construction is independent of the subsequent optimizer. Score 1 only for the minor co-authorship of the runtime black box, which is not load-bearing for the central compression theorem.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The paper is pure algorithms; it introduces no free parameters fitted to data and no physical entities. The only non-standard ingredients are the computational-model assumptions (word-RAM with O(1)-word dyadics) and the black-box separable min-cost-flow theorem of Dong et al., both of which are domain assumptions rather than ad-hoc inventions.

axioms (3)
  • domain assumption Word-RAM model with word size Θ(log n) and a global precision parameter B = O(log n) such that every input coordinate belongs to 2^{-B}ℤ and fits in O(1) machine words.
    Stated in Section 2 and required for the exact ĕO(n) claim of Theorem 1.4; without it the cost scaling and arithmetic model are undefined.
  • domain assumption Existence of a nearly-linear-time randomized min-cost-flow algorithm for 1/2-separable graph families with polynomially bounded integral costs and capacities (Dong et al. [DGG+25]).
    Invoked as a black box after Theorem 1.6 to obtain the expected ĕO(n) bound; the geometric candidate set itself does not depend on it.
  • standard math Standard facts of planar geometry and combinatorial optimization: ℓp-norm comparisons, grid-point counting in balls, existence of an optimum for finite-cost injective assignments, integral flow decomposition.
    Used throughout Sections 2–6; all are classical and cited or proved inline.

pith-pipeline@v1.1.0-grok45 · 25841 in / 2738 out tokens · 23555 ms · 2026-07-14T09:52:43.833281+00:00 · methodology

0 comments
read the original 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$.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 7 canonical work pages · 3 internal anchors

  1. [1]

    [ACX19] Pankaj K

    doi:10.1145/3519935.3519977; arXiv:2204.03875. [ACX19] Pankaj K. Agarwal, Hsien-Chih Chang, and Allen Xiao. Efficient algorithms for geometric partial matching. In 35th International Symposium on Computational Geometry (SoCG) , volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:14. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur I...

    doi:10.1145/3519935.3519977

  2. [2]

    Efficient Algorithms for Geometric Partial Matching

    doi:10.4230/LIPIcs.SoCG.2019.6; arXiv:1903.09358. [CJ91] Siu-Wing Cheng and Ravi Janardan. Efficient maintenance of the union of intervals on a line, with applications. Journal of Algorithms, 12(1):57–74,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.socg.2019.6 2019

  3. [3]

    27 [CKL+22] Li Chen, Rasmus Kyng, Yang P

    doi:10.1016/0196- 6774(91)90023-R. 27 [CKL+22] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 612–623,

    doi:10.1016/0196-

  4. [4]

    [EKSS15] David Eppstein, Marc van Kreveld, Bettina Speckmann, and Frank Staals

    doi:10.1145/3744639. [EKSS15] David Eppstein, Marc van Kreveld, Bettina Speckmann, and Frank Staals. Improved grid map layout by point set matching. International Journal of Computational Ge- ometry & Applications , 25(2):101–122,

    work page doi:10.1145/3744639

  5. [5]

    [FL20] Kyle Fox and Jiashuai Lu

    doi:10.1142/S0218195915500077. [FL20] Kyle Fox and Jiashuai Lu. A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread. In 36th International Symposium on Computational Geometry (SoCG), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 45:1–45:18. Schloss Dagstuhl–Leibniz-Zentr...

    work page doi:10.1142/s0218195915500077

  6. [6]

    A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread

    doi:10.4230/LIPIcs.SoCG.2020.45; arXiv:1907.04426. [GGH+97] Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, and Paul J. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proceedings of the 13th Annual Symposium on Computational Geometry (SoCG) , pages 284–293,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.socg.2020.45 2020

  7. [7]

    A fast optimal double row le- galization algorithm

    [HNS21] Stefan Hougardy, Meike Neuwohner, and Ulrike Schorr. A fast optimal double row le- galization algorithm. In Proceedings of the 2021 International Symposium on Physical Design (ISPD), pages 23–30,

    2021

  8. [8]

    [HPAB+24] Yen-Hsiang Huang, Sai Pentapati, Anthony Agnesina, Moritz Brunion, and Sung Kyu Lim

    doi:10.1145/3439706.3447044; arXiv:2101.08561. [HPAB+24] Yen-Hsiang Huang, Sai Pentapati, Anthony Agnesina, Moritz Brunion, and Sung Kyu Lim. On legalization of die bonding bumps and pads for 3-D ICs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 43(9):2741–2754,

    work page doi:10.1145/3439706.3447044

  9. [9]

    Snapping Graph Drawings to the Grid Optimally

    doi:10.1007/978-90-481- 9591-6. [LDW16] Andr´ e L¨ offler, Thomas C. van Dijk, and Alexander Wolff. Snapping graph drawings to the grid optimally. CoRR, abs/1608.08844,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/978-90-481-

  10. [10]

    [SA12] R

    doi:10.1137/0136016. [SA12] R. Sharathkumar and Pankaj K. Agarwal. Algorithms for the transportation problem in geometric settings. In Proceedings of the 23rd Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 306–317,

    doi:10.1137/0136016

  11. [11]

    [SGR+25] Yunqi Shi, Chengrui Gao, Wanqi Ren, Peng Xie, Siyuan Xu, Ke Xue, Mingxuan Yuan, Chao Qian, and Zhi-Hua Zhou

    doi:10.1137/1.9781611973099.29. [SGR+25] Yunqi Shi, Chengrui Gao, Wanqi Ren, Peng Xie, Siyuan Xu, Ke Xue, Mingxuan Yuan, Chao Qian, and Zhi-Hua Zhou. Open3DBench: Open-source benchmark for 3D-IC backend implementation and PPA evaluation. arXiv:2503.12946v2, revised

    Pith/arXiv arXiv doi:10.1137/1.9781611973099.29

  12. [12]

    [VYP+25] Pruek Vanna-iampikul, Junsik Yoon, Chaeryung Park, Gary Yeap, and Sung Kyu Lim

    doi:10.1145/1353629.1353640. [VYP+25] Pruek Vanna-iampikul, Junsik Yoon, Chaeryung Park, Gary Yeap, and Sung Kyu Lim. Placement-aware 3D net-to-pad assignment for array-style hybrid bonding 3D ICs. In Proceedings of the 2025 International Symposium on Physical Design (ISPD) , pages 200–208,

    work page doi:10.1145/1353629.1353640 2025