{"id":"b1fc7236-d948-4dda-a54c-6b93ecf96e9b","arxiv_id":"2607.10703","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A universal O(n)-size candidate set for infinite-grid ℓp matching yields a randomized exact ĕO(n)-time algorithm for the rectilinear case via sparse min-cost flow.","lead":"The paper shows how to match n points in the plane to distinct integer-grid sites under Manhattan cost in expected nearly-linear time. It first compresses the infinite grid to O(n) candidate sites that still contain an optimal assignment for every ℓp norm, then routes the ℓ₁ case through a sparse separable min-cost flow.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the black-box MCF citation as the sole external point that could affect the strongest runtime claim, while recognizing that the geometric compression (the paper’s main technical contribution) stands independently. My re-examination of the pruning safety lemmas, the simultaneous-update argument, the charging freshness/disjointness lemmas, the final candidate-set enumeration, and the path-decomposition equality for the sparse ℓ1 network finds no additional load-bearing gap. The model assumptions (O(1)-word dyadic coordinates, B=O(log n)) are explicit and handled by the normalization appendix. Consequently the ACCEPT verdict with high confidence remains appropriate; no adjustment is warranted.","tokens_in":21828,"tokens_out":498,"duration_ms":4823,"concrete_test":"Independently re-derive the high-radius lattice-point bound of Lemma 5.8 from the definitions of It, Xt, Vt and the packing lemma 5.2 (without relying on the narrative summary in §5.3); confirm that the geometric expansions with b=12 keep NΔt(Vt) inside a constant-factor enlargement whose area remains O(|Xt|). If the O(n) bound fails under this re-derivation, the candidate-set size claim weakens.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central geometric claim (Theorem 1.2) is self-contained: iterated safe pruning with the square-covering estimator yields a p-independent O(n)-size candidate set in O(n log^{2} n) time, with the high-radius area bound proved by the charging argument of Lemmas 5.3–5.8 (freshness of Xt, disjointness, coverage of U(2)T). The ℓ1 reduction (Theorem 1.6) produces an O(n)-edge 1/2-separable network whose optimum equals the matching cost. The only external dependency for the ẽO(n) runtime is the black-box separable MCF of Dong et al., which the paper invokes under the stated polynomially-bounded integral costs after scaling by 2B. That dependency is standard and does not undermine the candidate-set theorem or the reduction. No internal inconsistency, hidden non-uniformity over p, or gap in the charging/separability arguments appears on a careful reading.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":22024,"tokens_out":853,"duration_ms":18573,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is unusually clean for a first arXiv version; the geometric core is self-contained and the only external dependency (Dong et al. MCF) is used correctly under the stated polynomial-cost hypothesis. I see no novelty or citation issues. Fit for a top algorithms/geometry journal is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The real advance here is Theorem 1.2: in O(n log^{2} n) time you get an O(n)-size set C that simultaneously contains an optimal assignment for every ℓp. That removes the quadratic nearest-grid blow-up that has been the default reduction, and the bound is tight. The iterated safe-pruning argument (initial radius 3√n, square-covering estimator, geometric shrink of test radii, then the charging over dense regions via the Xt sets and the coverage of U(2)T) is elementary, continuous, and p-independent. I checked the chain from Lemmas 3.1–3.4 through 5.2–5.12; it holds.\n\nFor the rectilinear case they then build a linear-size sparse network whose optimum equals the matching cost (Theorem 1.6) and feed it to the Dong et al. separable min-cost-flow algorithm. Under the stated word-RAM model with O(log n) fractional bits you get expected Õ(n) exact time. That is optimal up to logs once you have to output the assignment. The same C immediately gives the (1+ε) approximation for integer p via ACX19. Appendices on unavailable sites and thick windows are short and useful.\n\nSoft spots are minor and proportional. The strongest runtime claim is black-box on DGG+25; if that solver’s guarantees do not apply to the residual graphs or cost bounds, the Õ(n) collapses while the candidate set and the reduction remain valid. There is also an alternative n^{1+o(1)} route via range trees + CKL that does not need separability. No experiments, but this is pure theory and the proofs are self-contained. Citations look honest; the finite-matching and planar-flow literature is used correctly as engines, not as definitions of the optimum.\n\nThis is for people who care about geometric matching, transportation, or VLSI-style legalization. A serious referee should see it. I would accept for peer review and would cite the candidate-set theorem myself.","headline":"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.","tokens_in":22657,"tokens_out":541,"would_cite":true,"duration_ms":7647,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","68Q25","90C27","05C85"],"pacs":[],"model":"grok-4.5","headline":"A linear set of grid points captures an optimal assignment for every ℓp norm, unlocking nearly-linear exact rectilinear matching.","keywords":["rectilinear matching","integer grid","candidate set","safe pruning","minimum-cost flow","geometric bipartite matching","ℓp norms","legalization"],"falsifier":"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.","tokens_in":22689,"feed_emoji":"▦","tokens_out":704,"duration_ms":5766,"temperature":0.7,"pith_summary":"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.","feed_headline":"Linear grid candidates unlock nearly-linear exact matching","feed_subtitle":"One O(n)-size set works for every ℓp norm; rectilinear case runs in expected Õ(n) time","key_machinery":"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.","core_discovery":"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.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["O(n) lattice set captures optimal ℓp grid matchings for all p","Compress infinite grid to O(n) candidates in O(n log² n)","Nearly-linear exact ℓ1 matching via linear sparse network","Finite O(n) candidates yield expected Õ(n) rectilinear algorithm","Same O(n) set gives (1+ε) approx for every fixed integer p"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["O(n) lattice set captures optimal ℓp grid matchings for all p","Compress infinite grid to O(n) candidates in O(n log² n)","Nearly-linear exact ℓ1 matching via linear sparse network","Finite O(n) candidates yield expected Õ(n) rectilinear algorithm","Same O(n) set gives (1+ε) approx for every fixed integer p"]},"model":"grok-4.5","effort":"low","cost_usd":0.006516,"raw_usage":{"total_tokens":1674,"prompt_tokens":834,"num_sources_used":0,"completion_tokens":106,"cost_in_usd_ticks":65160000,"prompt_tokens_details":{"text_tokens":834,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":734,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":834,"tokens_out":106,"duration_ms":6881,"temperature":1.0,"reasoning_tokens":734,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T09:52:43.833281+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}