DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2025.4

A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains

Authors: Pankaj K. Agarwal, Boris Aronov, Olivier Devillers, Christian Knauer, and Guillaume Moroz

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

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-α}).

Cite as

Pankaj K. Agarwal, Boris Aronov, Olivier Devillers, Christian Knauer, and Guillaume Moroz. A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2025.4,
  author =	{Agarwal, Pankaj K. and Aronov, Boris and Devillers, Olivier and Knauer, Christian and Moroz, Guillaume},
  title =	{{A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.4},
  URN =		{urn:nbn:de:0030-drops-231561},
  doi =		{10.4230/LIPIcs.SoCG.2025.4},
  annote =	{Keywords: Terrain similarity, volume computation, polynomial interpolation, geometric cuttings, bivariate multipoint evaluation}
}

Search Results

Documents authored by Moroz, Guillaume

A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains

Abstract

Cite as

Thanks for your feedback!

Could not send message