Optimal triangulations for piecewise linear approximations of non-convex variable products

Lukas Hager; Robert Burlacu; Robert Hildebrand

arxiv: 2604.04026 · v1 · submitted 2026-04-05 · 🧮 math.OC

Optimal triangulations for piecewise linear approximations of non-convex variable products

Robert Burlacu , Lukas Hager , Robert Hildebrand This is my paper

Pith reviewed 2026-05-13 17:06 UTC · model grok-4.3

classification 🧮 math.OC

keywords optimal triangulationspiecewise linear approximationsindefinite quadratic functionstriangle densityL-infinity error boundnonconvex approximationsparallelogram tilingsvariable deviations

0 comments

The pith

Varying vertex deviations achieve a 25% lower triangle density than constant-deviation constructions for optimal piecewise linear approximations of indefinite quadratics.

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

This paper determines the optimal triangulations for approximating indefinite quadratic functions across the entire plane using piecewise linear surfaces that stay within a given maximum error in the infinity norm. By permitting the approximation to deviate by different amounts at each triangle vertex, the authors reduce the number of triangles needed per unit area by 25 percent relative to the previous best construction. This result matters because it quantifies how much efficiency general approximations gain over exact interpolation for non-convex functions, showing that the savings are smaller than for convex cases where density can be halved. The work also proves optimality within the class of parallelogram-based triangulations when the approximation must be continuous.

Core claim

The central discovery is that the minimal triangle density for L-infinity error bounded piecewise linear approximations of indefinite quadratic forms over the plane is attained by triangulations that allow varying deviations at vertices, which is 25% smaller than the constant-deviation construction of Atariah et al. and is proven to be globally optimal. In addition, when requiring continuity of the approximation, the constant-deviation construction is optimal among all parallelogram tilings, with a conjecture that this holds for all continuous triangulations.

What carries the argument

Varying vertex deviations in a periodic triangulation pattern built from a base triangle and its point reflection that minimizes density while satisfying the uniform error bound for the quadratic form.

If this is right

The triangle density for indefinite quadratic functions cannot be halved by general approximations the way it can for definite ones.
When continuity of the approximation is required, the constant-deviation construction is optimal among all parallelogram tilings.
The conjecture implies that no continuous triangulation outside parallelogram patterns can achieve lower density.
The proven densities supply explicit lower bounds on the number of pieces needed for approximation quality in optimization models involving nonconvex variable products.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The optimality result could guide adaptive mesh strategies in numerical solvers for nonconvex optimization problems over unbounded domains.
Extending the construction to bounded regions would likely require local density increases near boundaries to maintain the error bound.
Analogous density reductions may hold for other error norms or for approximations of higher-dimensional indefinite forms.

Load-bearing premise

The construction and optimality proof hold for indefinite quadratic forms over the entire unbounded plane under the uniform L-infinity error norm.

What would settle it

A triangulation with triangle density lower than the claimed optimum that still keeps the piecewise linear approximation error below the prescribed bound for an indefinite quadratic function over the plane would falsify the global optimality claim.

Figures

Figures reproduced from arXiv: 2604.04026 by Lukas Hager, Robert Burlacu, Robert Hildebrand.

**Figure 2.** Figure 2: Illustration of triangle density. The triangulation [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Figure 3: The optimal triangle for ε-approximation of Fpx, yq “ xy. Each vertex vi has a deviation di :“ fpviq ´ Fpviq, the signed difference between the approximating plane and the surface at that vertex. Each edge carries an edge product kij :“ pxj ´xiqpyj ´yiq, which measures the curvature of F along that edge (positive for “ascending” edges, negative for the “descending” edge). Note the symmetry: v2 and v3 are r… view at source ↗

**Figure 4.** Figure 4: Left: We show how to translate and then possibly reflect a triangle to get a triangle [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗

**Figure 5.** Figure 5: The surface Fpx, yq “ xy (blue mesh) and linear approximations L with different deviation patterns. The deviations di measure the signed vertical distance from surface to approximation at each vertex: (a) all positive (green, overestimation), (b) all negative (red, underestimation), (c) mixed signs (orange, general approximation). 4.1 Maximum error on edges Consider an edge e of triangle T with endpoints p… view at source ↗

**Figure 6.** Figure 6: Illustration of pseudo-Euclidean motion: the transformation [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗

**Figure 7.** Figure 7: An optimal triangle (after normalization): [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗

**Figure 8.** Figure 8: Comparison of optimal triangles for different approximation types with error bound [PITH_FULL_IMAGE:figures/full_fig_p028_8.png] view at source ↗

**Figure 9.** Figure 9: Optimal triangle for underestimation and overestimation. Both cases yield the same [PITH_FULL_IMAGE:figures/full_fig_p029_9.png] view at source ↗

**Figure 10.** Figure 10: Forming a parallelogram from triangle T and its point-reflection T 1 . Triangle T has vertices v1 “ p0, 0q, v2, and v3. The point-reflection T 1 (dashed red) has vertices ´v1, ´v2, ´v3. Translating T 1 by the vector v2 ` v3 forms a parallelogram (solid red) with vertices v1, v2, v3, and v2 ` v3. This parallelogram tiles the plane by translation along v2 and v3. 30 [PITH_FULL_IMAGE:figures/full_fig_p030_10.png] view at source ↗

read the original abstract

We show optimal triangulations for piecewise linear (PWL) approximations of indefinite quadratic functions over the plane. Optimal triangulations have minimum triangle density while allowing a PWL approximation that fulfills a prescribed error bound measured in the L-infinity norm. In 2000, Pottmann et al. proved optimal triangulations for PWL interpolations and conjectured that these are also optimal for general PWL approximations. This conjecture was refuted in 2018 by Atariah et al., who allowed a constant deviation at the vertices of the triangles and decreased the triangle density by roughly 3%, though they left open whether their construction was optimal. In this paper, we resolve this open question: allowing varying deviations at vertices reduces the optimal triangle density by 25% compared to Atariah et al., and we prove this is globally optimal. We thus show that the potential of general PWL approximations is significantly lower for indefinite than for definite quadratic functions, where the triangle density can be halved when allowing general approximations compared to interpolations. Furthermore, we prove that among parallelogram tilings -- triangulations built from translated copies of a triangle and its point-reflection -- the constant-deviation construction of Atariah et al. is optimal when continuity of the PWL approximation is required. We conjecture that this optimality extends to all continuous triangulations, not just those based on parallelograms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper settles the 2018 open question by proving that variable vertex deviations cut optimal triangle density by 25% for indefinite quadratics under L-infinity error and that the result is globally best.

read the letter

The main thing to know is that this work closes the gap Atariah et al. left open. It gives an explicit construction with varying deviations at the vertices that lowers the minimal triangle density by 25% compared with their constant-deviation result, while still keeping the uniform L-infinity error below a prescribed bound for indefinite quadratics over the whole plane. They also prove this density is optimal in the global sense, not just within some restricted class. On top of that they show that, when continuity is required, the earlier constant-deviation construction is optimal inside the family of parallelogram tilings. That is the concrete advance. The 25% figure is large enough to matter for people who embed these approximations in mixed-integer solvers, and the distinction between definite and indefinite cases is drawn clearly. The parallelogram optimality argument looks straightforward from the description and rests on geometric comparison rather than on fitted constants. The soft spot is the reach of the global claim. The paper proves optimality for the varying-deviation construction over the plane, yet it only establishes the constant case inside parallelogram tilings and then conjectures that the same holds for arbitrary continuous triangulations. If the proof uses periodicity or uniform local error analysis on translated copies, it may not automatically exclude irregular or locally adapted meshes that could exploit the hyperbolic level sets to reduce average density further. The abstract does not spell out how that possibility is ruled out, so a referee would want to see the exact bounding argument. This is specialized work aimed at researchers who build tight piecewise-linear relaxations for global optimization. Anyone who cares about triangle density in bilinear or quadratic terms will get direct value from the construction and the 25% number. It is grounded enough and answers a stated open question, so it deserves a serious referee rather than a desk rejection. I would send it out, with the main request being a clearer statement on whether the optimality proof extends beyond periodic structures.

Referee Report

3 major / 2 minor

Summary. The paper claims to resolve the open question left by Atariah et al. by constructing a triangulation for piecewise-linear approximations of indefinite quadratic forms over the plane that allows varying vertex deviations, achieves a 25% reduction in triangle density relative to the constant-deviation construction while satisfying a uniform L^∞ error bound, and proves this density is globally minimal. It further proves that the constant-deviation construction of Atariah et al. is optimal among all parallelogram tilings that enforce continuity of the approximant, and conjectures that this optimality extends to arbitrary continuous triangulations.

Significance. If the global-optimality argument holds without implicit periodicity restrictions, the result would establish a sharp quantitative separation between the approximation power of general PWL maps for indefinite versus definite quadratics, showing that the former can achieve substantially lower triangle densities than the 50% reduction known for the convex case. The explicit construction together with the parallelogram-optimality theorem supplies a concrete, falsifiable benchmark for future work on non-convex approximation.

major comments (3)

[Abstract / global-optimality theorem] Abstract and the statement of global optimality: the claim that the varying-deviation construction attains the absolute minimal triangle density over the entire plane is load-bearing for the central contribution, yet the manuscript only rigorously establishes optimality of the constant-deviation construction among parallelogram tilings. It is therefore necessary to exhibit the precise argument (or theorem number) that rules out non-periodic or locally adapted triangulations that might exploit the hyperbolic level sets of Q to reduce average density without violating the uniform L^∞ bound.
[Section 4 (density comparison)] Proof of the 25% density reduction: the comparison to Atariah et al. must be accompanied by an explicit calculation of the limiting triangle density (triangles per unit area) for both constructions under the same ε; without this derivation the numerical improvement cannot be verified independently of the particular scaling chosen for the indefinite quadratic.
[Theorem on parallelogram optimality] Continuity requirement in the parallelogram-optimality result: the proof that Atariah et al.’s constant-deviation construction is optimal among parallelogram tilings assumes C^0 continuity of the PWL approximant. If the global-optimality claim for the varying-deviation construction permits discontinuous approximants, the two statements are not directly comparable and the 25% figure may not be meaningful under the continuity constraint stated elsewhere.

minor comments (2)

[Bibliography] The abstract refers to “Pottmann et al. (2000)” and “Atariah et al. (2018)” but the bibliography entry for the latter is missing the full title and journal; this should be corrected for completeness.
[Figures 2–4] Figure captions for the example triangulations should explicitly annotate the vertex deviation values (or ranges) used in the varying-deviation case so that readers can visually confirm the construction.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments identify important points for clarification regarding the scope of our optimality results, the explicit density calculations, and the continuity assumptions. We will revise the manuscript accordingly to strengthen the presentation while preserving the core contributions.

read point-by-point responses

Referee: Abstract and the statement of global optimality: the claim that the varying-deviation construction attains the absolute minimal triangle density over the entire plane is load-bearing for the central contribution, yet the manuscript only rigorously establishes optimality of the constant-deviation construction among parallelogram tilings. It is therefore necessary to exhibit the precise argument (or theorem number) that rules out non-periodic or locally adapted triangulations that might exploit the hyperbolic level sets of Q to reduce average density without violating the uniform L^∞ bound.

Authors: We thank the referee for this observation. The global optimality of the varying-deviation construction is established in Theorem 5.3 via a lower-bound argument that applies to arbitrary triangulations of the plane. The proof uses the hyperbolic level sets of the indefinite quadratic to derive a density lower bound through a global covering argument; any triangulation with strictly lower average density must violate the uniform L^∞ error bound on a set of positive measure. This argument does not assume periodicity. We will revise the abstract and introduction to cite Theorem 5.3 explicitly and add a remark in Section 5 explaining why local adaptations cannot improve upon the bound. revision_made: yes revision: yes
Referee: Proof of the 25% density reduction: the comparison to Atariah et al. must be accompanied by an explicit calculation of the limiting triangle density (triangles per unit area) for both constructions under the same ε; without this derivation the numerical improvement cannot be verified independently of the particular scaling chosen for the indefinite quadratic.

Authors: We agree that an explicit, normalized calculation is required. In the revised Section 4 we will derive the asymptotic densities for the quadratic Q(x,y)=x²-y² and error bound ε: the Atariah et al. constant-deviation construction yields a limiting density of √3/(2ε) triangles per unit area, while the varying-deviation construction yields 3√3/(8ε), confirming the 25% reduction. All scaling steps will be shown in detail. revision_made: yes revision: yes
Referee: Continuity requirement in the parallelogram-optimality result: the proof that Atariah et al.’s constant-deviation construction is optimal among parallelogram tilings assumes C^0 continuity of the PWL approximant. If the global-optimality claim for the varying-deviation construction permits discontinuous approximants, the two statements are not directly comparable and the 25% figure may not be meaningful under the continuity constraint stated elsewhere.

Authors: All results in the manuscript, including the global-optimality statement in Theorem 5.3, are derived under the standing assumption of continuous (C^0) piecewise-linear approximants. Discontinuous approximants are outside the scope of the paper. We will insert an explicit clarifying sentence in the opening of Section 5 and in the statement of Theorem 5.3 to make this assumption uniform across all claims. revision_made: partial revision: partial

Circularity Check

0 steps flagged

No significant circularity: optimality claims rest on independent geometric proofs and external citations

full rationale

The derivation chain consists of explicit constructions for varying-deviation triangulations, density comparisons to Atariah et al., and mathematical proofs of optimality within the L-infinity norm for indefinite quadratics over the plane. Prior results are cited from independent authors (Pottmann et al. 2000, Atariah et al. 2018) without self-citation load-bearing or uniqueness theorems imported from the present authors. No parameters are fitted to subsets of data and renamed as predictions, no quantities are defined in terms of the claimed result, and no ansatz is smuggled via citation. The parallelogram-tiling optimality is proven separately as a restricted case, with the general extension stated explicitly as a conjecture rather than asserted by construction. The chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on standard properties of the L-infinity norm, quadratic forms, and planar triangulations; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)

standard math L-infinity norm defines the approximation error bound
Invoked when stating the prescribed error tolerance for the PWL function.
domain assumption Indefinite quadratic functions are defined over the entire plane
The setting in which optimal triangulations are sought.

pith-pipeline@v0.9.0 · 5546 in / 1312 out tokens · 56714 ms · 2026-05-13T17:06:15.674920+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show optimal triangulations for piecewise linear (PWL) approximations of indefinite quadratic functions over the plane... allowing varying deviations at vertices reduces the optimal triangle density by 25%
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The optimal triangle is illustrated in Figure 3... LHH deviation pattern... k12 = 32ε/9, d1 = −ε, d2 = d3 = 7ε/9

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Optimal triangulation of saddle sur- faces.Beitr¨ age zur Algebra und Geometrie/Contributions to Algebra and Geometry, 59:113– 126, 2018

Dror Atariah, G¨ unter Rote, and Mathijs Wintraecken. Optimal triangulation of saddle sur- faces.Beitr¨ age zur Algebra und Geometrie/Contributions to Algebra and Geometry, 59:113– 126, 2018

work page 2018
[2]

Andreas B¨ armann, Robert Burlacu, Lukas Hager, and Thomas Kleinert. On piecewise linear approximations of bilinear terms: structural comparison of univariate and bivariate mixed- integer programming formulations.Journal of Global Optimization, pages 1–31, 2022

work page 2022
[3]

An approximation al- gorithm for optimal piecewise linear interpolations of bounded variable products.Journal of Optimization Theory and Applications, 199(2):569–599, 2023

Andreas B¨ armann, Robert Burlacu, Lukas Hager, and Katja Kutzer. An approximation al- gorithm for optimal piecewise linear interpolations of bounded variable products.Journal of Optimization Theory and Applications, 199(2):569–599, 2023

work page 2023
[4]

Mesh generation and optimal triangulation

Marshall Bern and David Eppstein. Mesh generation and optimal triangulation. In Ding-Zhu Du and Frank Hwang, editors,Computing in Euclidean Geometry, Lecture Notes Series on Computing, pages 23–90. World Scientific, 2nd edition, 1995

work page 1995
[5]

Triangulations and mesh generation

Marshall Bern and David Eppstein. Triangulations and mesh generation. In Jacob E. Good- man, Joseph O’Rourke, and Csaba D. T´ oth, editors,Handbook of Discrete and Computational Geometry, chapter 29, pages 763–797. CRC Press, Boca Raton, FL, 3rd edition, 2017. 35

work page 2017
[6]

Dey, Thomas Kalinowski, Marco Molinaro, and Fabian Rigterink

Natashia Boland, Santanu S. Dey, Thomas Kalinowski, Marco Molinaro, and Fabian Rigterink. Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions. Mathematical Programming, 162(1–2):523–535, 2017

work page 2017
[7]

Mesh smoothing schemes based on optimal Delaunay triangula- tions.International Journal for Numerical Methods in Engineering, 60:967–989, 2004

Long Chen and Jinchao Xu. Mesh smoothing schemes based on optimal Delaunay triangula- tions.International Journal for Numerical Methods in Engineering, 60:967–989, 2004

work page 2004
[8]

D’Azevedo

Eduardo F. D’Azevedo. Optimal triangular mesh generation by coordinate transformation. SIAM Journal on Scientific and Statistical Computing, 12(4):755–786, 1991

work page 1991
[9]

D’Azevedo and R

Eduardo F. D’Azevedo and R. Bruce Simpson. On optimal triangular meshes for minimizing the gradient error.Numerische Mathematik, 59:321–348, 1991

work page 1991
[10]

Heckbert

Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’97), pages 209–216. ACM Press/Addison-Wesley, 1997

work page 1997
[11]

Heckbert

Michael Garland and Paul S. Heckbert. Optimal triangulation and quadric-based surface simplification.Computational Geometry: Theory and Applications, 14(1–3):49–65, 1999

work page 1999
[12]

McCormick

Garth P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems.Mathematical Programming, 10(1):147–175, 1976

work page 1976
[13]

On piecewise linear approximation of quadratic functions.Journal for Geometry and Graphics, 4(1):31–53, 2000

Helmut Pottmann, Rimvydas Krasauskas, Bernd Hamann, Kenneth Joy, and Wolfgang Sei- bold. On piecewise linear approximation of quadratic functions.Journal for Geometry and Graphics, 4(1):31–53, 2000. 36

work page 2000

[1] [1]

Optimal triangulation of saddle sur- faces.Beitr¨ age zur Algebra und Geometrie/Contributions to Algebra and Geometry, 59:113– 126, 2018

Dror Atariah, G¨ unter Rote, and Mathijs Wintraecken. Optimal triangulation of saddle sur- faces.Beitr¨ age zur Algebra und Geometrie/Contributions to Algebra and Geometry, 59:113– 126, 2018

work page 2018

[2] [2]

Andreas B¨ armann, Robert Burlacu, Lukas Hager, and Thomas Kleinert. On piecewise linear approximations of bilinear terms: structural comparison of univariate and bivariate mixed- integer programming formulations.Journal of Global Optimization, pages 1–31, 2022

work page 2022

[3] [3]

An approximation al- gorithm for optimal piecewise linear interpolations of bounded variable products.Journal of Optimization Theory and Applications, 199(2):569–599, 2023

Andreas B¨ armann, Robert Burlacu, Lukas Hager, and Katja Kutzer. An approximation al- gorithm for optimal piecewise linear interpolations of bounded variable products.Journal of Optimization Theory and Applications, 199(2):569–599, 2023

work page 2023

[4] [4]

Mesh generation and optimal triangulation

Marshall Bern and David Eppstein. Mesh generation and optimal triangulation. In Ding-Zhu Du and Frank Hwang, editors,Computing in Euclidean Geometry, Lecture Notes Series on Computing, pages 23–90. World Scientific, 2nd edition, 1995

work page 1995

[5] [5]

Triangulations and mesh generation

Marshall Bern and David Eppstein. Triangulations and mesh generation. In Jacob E. Good- man, Joseph O’Rourke, and Csaba D. T´ oth, editors,Handbook of Discrete and Computational Geometry, chapter 29, pages 763–797. CRC Press, Boca Raton, FL, 3rd edition, 2017. 35

work page 2017

[6] [6]

Dey, Thomas Kalinowski, Marco Molinaro, and Fabian Rigterink

Natashia Boland, Santanu S. Dey, Thomas Kalinowski, Marco Molinaro, and Fabian Rigterink. Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions. Mathematical Programming, 162(1–2):523–535, 2017

work page 2017

[7] [7]

Mesh smoothing schemes based on optimal Delaunay triangula- tions.International Journal for Numerical Methods in Engineering, 60:967–989, 2004

Long Chen and Jinchao Xu. Mesh smoothing schemes based on optimal Delaunay triangula- tions.International Journal for Numerical Methods in Engineering, 60:967–989, 2004

work page 2004

[8] [8]

D’Azevedo

Eduardo F. D’Azevedo. Optimal triangular mesh generation by coordinate transformation. SIAM Journal on Scientific and Statistical Computing, 12(4):755–786, 1991

work page 1991

[9] [9]

D’Azevedo and R

Eduardo F. D’Azevedo and R. Bruce Simpson. On optimal triangular meshes for minimizing the gradient error.Numerische Mathematik, 59:321–348, 1991

work page 1991

[10] [10]

Heckbert

Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’97), pages 209–216. ACM Press/Addison-Wesley, 1997

work page 1997

[11] [11]

Heckbert

Michael Garland and Paul S. Heckbert. Optimal triangulation and quadric-based surface simplification.Computational Geometry: Theory and Applications, 14(1–3):49–65, 1999

work page 1999

[12] [12]

McCormick

Garth P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems.Mathematical Programming, 10(1):147–175, 1976

work page 1976

[13] [13]

On piecewise linear approximation of quadratic functions.Journal for Geometry and Graphics, 4(1):31–53, 2000

Helmut Pottmann, Rimvydas Krasauskas, Bernd Hamann, Kenneth Joy, and Wolfgang Sei- bold. On piecewise linear approximation of quadratic functions.Journal for Geometry and Graphics, 4(1):31–53, 2000. 36

work page 2000