REVIEW 3 major objections 3 minor 7 references
Proof of Correctness and Time Complexity Analysis of a Maximum Distance Transform Algorithm
T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A maximum distance transform can be computed by building the upper envelope of parabolas in average O(N) time.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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).
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 3.1, Eq. (7)] 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 3.3, Lemma 2 and Theorem 6] 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 3.4, average-case complexity] 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.
minor comments (3)
- [Algorithm 1, input and loops] 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 5, conclusion] 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 3.3, pseudo-code formatting] 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.
Circularity Check
No circularity: the derivation is self-contained and presents an independent algorithmic construction; the noted sign issue is a correctness concern, not circularity.
full rationale
The paper derives the maximum distance transform algorithm by direct construction: Equation 5 defines each parabola, Equation 7 solves the intersection condition Phi_p(x) = Phi_q(x) by algebra, and Algorithm 1 builds the upper envelope from those intersections. No parameter is fitted to data and then renamed a prediction; no result is defined in terms of the quantity it is supposed to derive; and no load-bearing premise is imported from a self-citation. The cited works are external: Felzenszwalb and Huttenlocher (2004) is a prior, independently published algorithm, and Sunic (2003) is an external combinatorial reference used only to count edges in an enumeration tree. The paper explicitly attributes both to their original authors rather than invoking uniqueness theorems or ansatze from the present authors' earlier work. The duality in Equation 6 is a standard identity, not a renaming that smuggles the conclusion in as an input. A separate reviewer concern is that Lemma 1's Equation 7 may contain a sign error in the denominator, so Algorithm 1 could compute wrong intersections on some instances. That is a mathematical correctness flaw in the derivation chain, but it is not circularity: the formula is obtained by solving the defining equation, not by assuming the algorithm's output. Since no step reduces to its own input by construction, the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (4)
- domain assumption All parabolas share a single quadratic coefficient alpha with alpha > 0 for the upward-opening maximum transform.
- domain assumption The upper envelope is defined on the whole real line and the ranges of envelope parabolas partition (-infinity, infinity).
- ad hoc to paper Every path in the enumerated tree of algorithm states is equally likely.
- standard math The algorithm's state graph is isomorphic to Sunic's Catalan family tree.
Cite this review
Pith. "Pith review of Proof of Correctness and Time Complexity Analysis of a Maximum Distance Transform Algorithm." pith.science (2026). https://pith.science/paper/VYEFL3H2
@misc{pith2026190801662,
author = {Pith},
title = {Pith review of: Proof of Correctness and Time Complexity Analysis of a Maximum Distance Transform Algorithm},
year = {2026},
howpublished = {\url{https://pith.science/paper/VYEFL3H2}},
note = {Machine review of arXiv:1908.01662}
}
read the original abstract
The distance transform algorithm is popular in computer vision and machine learning domains. It is used to minimize quadratic functions over a grid of points. Felzenszwalb and Huttenlocher (2004) describe an O(N) algorithm for computing the minimum distance transform for quadratic functions. Their algorithm works by computing the lower envelope of a set of parabolas defined on the domain of the function. In this work, we describe an average time O(N) algorithm for maximizing this function by computing the upper envelope of a set of parabolas. We study the duality of the minimum and maximum distance transforms, give a correctness proof of the algorithm and its runtime, and discuss potential applications.
Figures
Reference graph
Works this paper leans on
-
[1]
P. F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan. Object detection with discriminatively trained part based models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32 0 (9): 0 1627--1645, 2010
work page 2010
-
[2]
Face detection, pose estimation, and landmark localization in the wild
Xiangxin Zhu and Deva Ramanan. Face detection, pose estimation, and landmark localization in the wild. In CVPR, 2012
2012
-
[3]
Pedro F. Felzenszwalb and Daniel P. Huttenlocher. Distance transforms of sampled functions. Technical report, Cornell CS, 2004
work page 2004
-
[4]
Self-describing sequences and the catalan family tree
Zoran S uni\' c . Self-describing sequences and the catalan family tree. In The Electronic Journal of Combinatorics, 2003
work page 2003
-
[5]
@esa (Ref
\@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should not add it explicitly Type <Return> for now, but then later remove the command n...
-
[6]
\@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@first@sw \@firstoftwo \@ifundefined NAT@b*@#2 \@firstoftwo @num @NAT@ctr \@secondoft...
-
[7]
@open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibsetup #1 @NAT@ctr @ @openbib .11em \@plus.33em \@minus.07em 4000 4000 `\.\@m @bibit...
work page 2019
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.