2026-07-24T08:33:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23156 2025-06-20T06:28:17Z ddc:004 open_access

A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains Agarwal, Pankaj K. Aronov, Boris Devillers, Olivier Knauer, Christian Moroz, Guillaume Terrain similarity volume computation polynomial interpolation geometric cuttings bivariate multipoint evaluation We study the problem of computing the L₁-distance between two piecewise-linear bivariate functions f and g, defined over a bounded polygonal domain 𝕄 ⊂ ℝ², that is, computing the quantity ‖f-g‖₁ = ∫_𝕄 |f(x,y)-g(x,y)| dx dy. If f and g are defined by linear interpolation over triangulations 𝐓_f and 𝐓_g, respectively, of 𝕄 with a total of n triangles, we show that ‖f-g‖₁ can be computed in Õ(n^α) time, where α = max{(ω+1)/2, 8/5}, ω is the matrix multiplication exponent, and Õ notation hides factors of the form n^ε for any ε > 0. This bound holds for the currently best known value of ω, which is approximately 2.37. More generally, if the complexity of the overlay of 𝐓_f and 𝐓_g is κ, then the runtime of our algorithm is Õ(κ^{α-1}n^{2-α}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Boris Aronov and Olivier Devillers and Christian Knauer and Guillaume Moroz 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.4 urn:nbn:de:0030-drops-231561 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.4 eng https://creativecommons.org/licenses/by/4.0/legalcode