{"id":"7d6ad0f6-3d3c-43d6-bdeb-7723cfd22de6","arxiv_id":"1908.01662","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A max distance transform algorithm mirroring Felzenszwalb-Huttenlocher is proposed, but its intersection formula is sign-flipped and its average-case runtime proof relies on an unjustified uniform-state assumption.","lead":"This paper proposes an algorithm for computing the maximum distance transform, the upper envelope of a set of equal-curvature parabolas, with a claimed average O(N) runtime. The central intersection formula contains a sign error, so the algorithm as printed does not compute the stated transform.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's intersection formula (Eq. 7) has a sign error: the denominator should be 2α(q−p), not 2α(p−q); every insertion in Algorithm 1 uses the wrong sign, so the claimed correctness proof collapses.","rationale":"The reader's weakest assumption correctly identifies a sign error in the central intersection lemma. I confirmed the algebra independently: the expansion of Φ_p=Φ_q yields denominator 2α(q−p) with the paper's numerator, equivalently denominator 2α(p−q) with the negated numerator; Eq. 7 as written returns the negative of the true intersection. This is not a matter of convention or outside consensus; it is an internal inconsistency that makes Algorithm 1 produce wrong values on a trivial input. The average-case runtime argument (Section 3.4) is also unsupported—the tree enumeration assumes uniform likelihood and cites Catalan counts without a proven bijection—but the correctness flaw is sufficient to reject. I see no independent support (no code, no formal proof) that could mitigate the error. The verdict should remain REJECT; the reader's assessment does not need adjustment.","tokens_in":8002,"tokens_out":6172,"duration_ms":55773,"concrete_test":"Recompute the intersection algebraically for the two-point case p=0, q=1, α=1, β=0, I(0)=I(1)=0: Φ_0(x)=x² and Φ_1(x)=(1−x)² intersect at x=1/2, but Eq. 7 gives x=−1/2. This single evaluation falsifies Lemma 1 and shows Algorithm 1's insertion test (line 10) is applied at the wrong location.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Setting Φ_p(x)=Φ_q(x) and expanding gives (p−q)[α(p+q)−2αx+β] = I(q)−I(p), so the unique intersection is x = [I(q)−I(p)+α(q²−p²)+β(q−p)] / [2α(q−p)], equivalently [I(p)−I(q)+α(p²−q²)+β(p−q)] / [2α(p−q)]. Equation (7) instead uses numerator I(q)+αq²+βq − I(p)−αp²−βp over 2α(p−q), which is the negative of the correct value. Because Algorithm 1 (line 9) computes s with this formula and line 10 tests s against the envelope range, every inserted intersection is mirrored about the origin. The failure is immediate on a two-point instance: with I(0)=I(1)=0, α=1, β=0, the true upper envelope switches at x=0.5, but Algorithm 1 computes s=−0.5, giving the wrong transform value at x=0 (output 0 instead of 1). Lemma 2, which asserts the left/right ordering used throughout Theorem 6, is also incompatible with Eq. 7. No formal verification or reproducible implementation is provided, so the algebraic error is unmitigated. This is a load-bearing flaw in the central correctness claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes an algorithm for computing the maximum distance transform D(x)=max_p[I(p)+α(p−x)^2+β(p−x)] on 1D grids, and by separability on higher-dimensional grids. It claims an average-case O(N) runtime with worst-case O(N^2), gives a correctness proof based on the upper envelope of parabolas, and discusses duality with the minimum distance transform. The central algorithmic contribution is Algorithm 1 in Section 3.3.","tokens_in":8287,"tokens_out":6651,"duration_ms":67650,"significance":"If correct, an average O(N) algorithm for the maximum distance transform would be a useful complement to the Felzenszwalb–Huttenlocher minimum transform and would have applications in computer vision. The paper makes a genuine effort to provide a self-contained algorithm, correctness proof, and complexity analysis. However, the central algebraic formula in Lemma 1 is wrong, and a simple two-point example shows that Algorithm 1 returns an incorrect distance transform value. The average-case complexity claim also rests on an unjustified uniformity assumption. No executable implementation or machine-checked proof is supplied, so the algebraic error is not mitigated by external validation.","major_comments":[{"comment":"The intersection formula in Eq. (7) is algebraically incorrect. Setting Φ_p(x)=Φ_q(x) gives x = [I(q)−I(p)+α(q^2−p^2)+β(q−p)] / [2α(q−p)], which equals [I(q)+αq^2+βq − (I(p)+αp^2+βp)] / [2α(q−p)]. Eq. (7) instead divides by 2α(p−q), which is the negative of the correct denominator. Since Algorithm 1 line 9 uses exactly this formula in every insertion step, the sign error is load-bearing. For I(0)=I(1)=0, α=1, β=0, the formula returns s=−0.5 rather than 0.5, and Algorithm 1 outputs DT[0]=0 while the true transform value is max(0^2,(1−0)^2)=1. Theorem 6 is therefore unsupported as written.","section":"Section 3.1, Eq. (7)"},{"comment":"Lemma 2 states an ordering of the two parabolas relative to their intersection point s_{p,q}; the statement is true only when s_{p,q} is the actual point of intersection. Lemma 1, however, supplies a different value for p<q (the negative of the true intersection), so Lemma 2 and Lemma 1 are inconsistent. Algorithm 1 relies on the Lemma 2 ordering through Lemma 3 and Corollaries 4–5 when deciding which parabolas to remove from the envelope in lines 10–15, so the envelope-update logic is not justified by the proof as given.","section":"Section 3.3, Lemma 2 and Theorem 6"},{"comment":"The average-case analysis assumes that every path in the enumerated tree is equally likely, and then averages edge weights uniformly. The paper provides no stochastic model of the input I and no argument that the tree paths occur with equal probability under any reasonable input distribution. Without a justification of this uniformity assumption, the claim that the average number of inner-loop iterations is O(1) is not established. The worst-case O(N^2) bound is elementary and correct, but the average-case claim is a separate contribution that lacks a valid proof.","section":"Section 3.4, average-case complexity"}],"minor_comments":[{"comment":"Algorithm 1 states the input grid as {0,1,...,N}, but the loops in lines 7 and 16 run only to N−1. The off-by-one should be clarified.","section":"Algorithm 1, input and loops"},{"comment":"The statement that the algorithm together with the minimum transform allows exact global optimization for 'any inference problem on quadratic functions' overstates the scope, since only transforms of the specific separable form in Eqs. (3)–(4) are addressed.","section":"Section 5, conclusion"},{"comment":"Line 16 of Algorithm 1 should be labeled as a separate 'for' loop, and the indentation of the 'while' loop should clearly show that it fills the transform array; the current pseudo-code layout is easy to misread.","section":"Section 3.3, pseudo-code formatting"}],"recommendation":"reject","confidential_remarks":"The central defect is an elementary sign error in Lemma 1 that a two-point numerical test would have exposed. Even after correcting Eq. (7), the average-case claim would still need a genuine probability model. As the manuscript stands, the main correctness result is false, so rejection is appropriate; a substantially revised version would be needed for reconsideration."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: Lemma 1's intersection formula has the denominator sign flipped. On the two-point instance I(0)=I(1)=0, α=1, β=0, the true upper envelope switches at x=0.5, but Eq. 7 returns s=-0.5, and Algorithm 1 produces DT[0]=0 instead of 1. That is not a cosmetic slip; every insertion uses this formula, so Theorem 6's correctness proof collapses.\n\nWhat the paper does well: it states the duality between max and min distance transforms honestly (Eq. 6), and the intended algorithm is a clean mirror image of Felzenszwalb-Huttenlocher. The exposition is readable and the geometric picture of upper envelopes is sensible. If the algebra were right, the average-case runtime claim would be the only meaningful new part.\n\nThe soft spots are serious. First, the sign error above is load-bearing. Lemma 3 and Corollaries 4–5 inherit the wrong orientation, and Lemma 2 is incompatible with Eq. 7 on the same two-point example. Second, the average-case argument is not a proof: it assumes equiprobability over a tree of possible inner-loop iteration counts without showing that any input distribution induces that weight, and the Catalan tree count is imported without a verified bijection. Third, the contribution is much smaller than claimed—as the authors themselves note, max is trivially the min of the negated function, so a correct algorithm would be FH applied to -I with the sign of the quadratic term flipped. There is no code, and no independent check of the runtime analysis.\n\nMy take: this paper should not be published in its current form. A referee would find a counterexample in minutes, and the main algorithmic idea is a known construction mirrored. It might be worth a one-page note once corrected to point out the duality, but as is it does not deserve a full referee cycle. Recommended action: desk reject; if an editor wanted to be thorough, one referee would confirm the algebra.","headline":"The core intersection formula has a sign error, so the algorithm returns wrong values on a trivial two-point input, and the runtime proof is too hand-wavy to rescue it.","tokens_in":8805,"tokens_out":4171,"would_cite":false,"duration_ms":38861,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A maximum distance transform can be computed by building the upper envelope of parabolas in average O(N) time.","keywords":["distance transform","upper envelope","parabolas","average-case complexity","Catalan family tree","deformable part models","quadratic optimization","1D grids"],"falsifier":"Take a two-point grid with I(0)=0, I(1)=1, α=1, β=0, run Algorithm 1, and compare every output against direct enumeration D(x)=max{I(0)+(0−x)^2, I(1)+(1−x)^2} for x in {0,1}. Any mismatch at those grid points settles whether the claimed correctness holds.","tokens_in":7797,"feed_emoji":"📐","tokens_out":6548,"duration_ms":63870,"temperature":0.7,"pith_summary":"This paper proposes Algorithm 1, an average-case O(N) procedure for computing the maximum distance transform D(x) = max_p [I(p) + α(p−x)^2 + β(p−x)] on a 1D grid, and extends the method to arbitrary dimensions. The central idea is that the maximum distance transform is the upper envelope of a set of parabolas, one per grid point, and that this envelope can be built incrementally by inserting each new parabola and removing those it dominates. The paper supplies an induction-based correctness proof and an average-case runtime analysis that counts possible envelope histories using Catalan-family-tree combinatorics. If the construction is correct, then the sign of the quadratic term stops being a barrier: both maximizing and minimizing quadratic functions over grids become efficient, which would relax model constraints in applications such as deformable part models.","feed_headline":"Computing max distance transforms in average O(N) time","feed_subtitle":"By building the parabolas' upper envelope, the maximum transform runs in average O(N) time, like the minimum transform.","key_machinery":"The upper envelope of a set of equal-curvature parabolas. The algorithm represents the envelope with two arrays: v[·] lists the indices of parabolas currently in the envelope, and z[·] stores the endpoints of their ranges so that parabola v[p] owns the interval (z[p+1], z[p]]. Each insertion requires the crossing point s of the candidate parabola with an existing envelope parabola; if that crossing lies within the existing parabola's range, the envelope is truncated at s and the new parabola is appended. The average-case analysis leans on the Catalan family tree, a combinatorial structure used to enumerate all possible sequences of inner-loop iterations and to derive that the average number of iterations is 3N/(N+2), which is O(1).","core_discovery":"The paper claims that the maximum distance transform equals the upper envelope of the parabolas Φ_p(x) = I(p) + α(p−x)^2 + β(p−x), and that Algorithm 1 computes this envelope in a single left-to-right pass. For each new grid point q, the algorithm computes the abscissa s at which the candidate parabola crosses an existing envelope parabola v[p]; if s falls inside that parabola's range, the candidate is inserted, later envelope parabolas are discarded, and the range boundaries are updated. The correctness proof is an induction on the number of grid points, with Lemma 1 supplying the intersection formula used in every insertion step and Lemma 2 supplying the ordering of parabolas around that intersection. The runtime analysis separates worst case O($N^{2}$) from average case O(N), with the average obtained by counting inner-loop iterations over a tree whose N-th level has Catalan-many edges.","pith_inferences":["The paper's own duality observation suggests a simpler route for maximizing upward-opening parabolas: negate the data, compute a minimum transform, and negate back; the proposed upper-envelope construction is an alternative to that reduction rather than the only available method.","If the envelope construction is verified, a natural next test is whether the Catalan-tree counting transfers to 2D separable transforms, where the algorithm performs 1D passes along rows and columns; the separability argument suggests it should, but the average-case count is not automatically preserved.","The average-case analysis enumerates all envelope histories as equally likely, so an input distribution that produces many deletions could still approach the O(N^2) worst case; profiling on adversarial intensity patterns would reveal how robust the average-case claim is in practice."],"forward_implications":["If correct, the maximum distance transform on a 1D grid has average-case O(N) cost, matching the classic minimum distance transform's runtime.","The 2D maximum distance transform can be computed by applying the 1D procedure once along columns and once along rows, in either order.","Combined with the minimum transform algorithm, the two procedures would allow optimizing quadratic functions over grids regardless of the sign of the quadratic terms, potentially loosening parameter constraints in deformable part models.","The worst-case runtime remains O(N^2), so the speed advantage is an average-case guarantee rather than a worst-case one."],"supporting_citations":[{"why":"Supplies the classic lower-envelope O(N) distance transform algorithm and the parabolic formulation that this paper adapts to the upper envelope.","marker":"[Felzenszwalb and Huttenlocher, 2004]"},{"why":"Provides the deformable part model context where quadratic scoring functions are optimized over grids, motivating the maximum distance transform.","marker":"[Felzenszwalb et al., 2010]"},{"why":"Provides a second application context in which quadratic distance transforms are used for pose estimation and landmark localization.","marker":"[Zhu and Ramanan, 2012]"},{"why":"Supplies the Catalan family tree counting results used to compute the average number of inner-loop iterations in the runtime analysis.","marker":"[Šunić, 2003]"}],"fun_headline_variants":["Max distance transform hits average O(N) via upper envelope","Upper envelope yields average O(N) max distance transform","Average O(N) for max distance transform, like minimum","Dual of min: max distance transform runs in average O(N)","Parabola upper envelope gives O(N) max transform on average"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is a single algebraic formula for where two parabolas intersect; if that formula's sign convention is wrong, the insertion rule and the envelope it builds are wrong.","fun_headline_variants_meta":{"raw":{"variants":["Max distance transform hits average O(N) via upper envelope","Upper envelope yields average O(N) max distance transform","Average O(N) for max distance transform, like minimum","Dual of min: max distance transform runs in average O(N)","Parabola upper envelope gives O(N) max transform on average"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00032,"raw_usage":{"total_tokens":1751,"prompt_tokens":843,"completion_tokens":908,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":824}},"tokens_in":459,"tokens_out":908,"duration_ms":8656,"temperature":1.0,"reasoning_tokens":824,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:08:48.230254+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-point grid with I(0)=0, I(1)=1, α=1, β=0, run Algorithm 1, and compare every output against direct enumeration D(x)=max{I(0)+(0−x)^2, I(1)+(1−x)^2} for x in {0,1}. Any mismatch at those grid points settles whether the claimed correctness holds.","supporting_citations":[],"review_version":1}