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

View

Pankaj K. Agarwal , Boris Aronov , Guillaume Moroz ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.4230/lipics.socg.2025.4

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

Related Topics

Concepts

Computer science Terrain Algorithm Geography Cartography

Metadata

Type: preprint
Language: en
Landing Page: https://hal.science/hal-04908634
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4406789551

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4406789551

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.4230/lipics.socg.2025.4

Digital Object Identifier
Title: A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-01-01

Full publication date if available
Authors: Pankaj K. Agarwal, Boris Aronov, Guillaume Moroz

List of authors in order
Landing page: https://hal.science/hal-04908634

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://hal.science/hal-04908634

Direct OA link when available
Concepts: Computer science, Terrain, Algorithm, Geography, Cartography

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4406789551
doi	https://doi.org/10.4230/lipics.socg.2025.4
ids.doi	https://doi.org/10.4230/lipics.socg.2025.4
ids.openalex	https://openalex.org/W4406789551
fwci	0.0
type	preprint
title	A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10996
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.5371999740600586
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1704
topics[0].subfield.display_name	Computer Graphics and Computer-Aided Design
topics[0].display_name	Computational Geometry and Mesh Generation
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.6401968002319336
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C161840515
concepts[1].level	2
concepts[1].score	0.5583147406578064
concepts[1].wikidata	https://www.wikidata.org/wiki/Q186131
concepts[1].display_name	Terrain
concepts[2].id	https://openalex.org/C11413529
concepts[2].level	1
concepts[2].score	0.4997837543487549
concepts[2].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[2].display_name	Algorithm
concepts[3].id	https://openalex.org/C205649164
concepts[3].level	0
concepts[3].score	0.11231258511543274
concepts[3].wikidata	https://www.wikidata.org/wiki/Q1071
concepts[3].display_name	Geography
concepts[4].id	https://openalex.org/C58640448
concepts[4].level	1
concepts[4].score	0.08428731560707092
concepts[4].wikidata	https://www.wikidata.org/wiki/Q42515
concepts[4].display_name	Cartography
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.6401968002319336
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/terrain
keywords[1].score	0.5583147406578064
keywords[1].display_name	Terrain
keywords[2].id	https://openalex.org/keywords/algorithm
keywords[2].score	0.4997837543487549
keywords[2].display_name	Algorithm
keywords[3].id	https://openalex.org/keywords/geography
keywords[3].score	0.11231258511543274
keywords[3].display_name	Geography
keywords[4].id	https://openalex.org/keywords/cartography
keywords[4].score	0.08428731560707092
keywords[4].display_name	Cartography
language	en
locations[0].id	pmh:oai:HAL:hal-04908634v1
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306402512
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	False
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	HAL (Le Centre pour la Communication Scientifique Directe)
locations[0].source.host_organization	https://openalex.org/I1294671590
locations[0].source.host_organization_name	Centre National de la Recherche Scientifique
locations[0].source.host_organization_lineage	https://openalex.org/I1294671590
locations[0].license	other-oa
locations[0].pdf_url
locations[0].version	submittedVersion
locations[0].raw_type	Conference papers
locations[0].license_id	https://openalex.org/licenses/other-oa
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name	Symposium on Computational Geometry (SoCG), Jun 2025, Kanazawa, Japan. pp.4:1-4:17, ⟨10.4230/LIPIcs.SoCG.2025.4⟩
locations[0].landing_page_url	https://hal.science/hal-04908634
locations[1].id	doi:10.4230/lipics.socg.2025.4
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S7407052059
locations[1].source.type	repository
locations[1].source.is_oa	False
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	Dagstuhl Research Online Publication Server
locations[1].source.host_organization
locations[1].source.host_organization_name
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.4230/lipics.socg.2025.4
indexed_in	datacite
authorships[0].author.id	https://openalex.org/A5058649592
authorships[0].author.orcid	https://orcid.org/0000-0002-9439-181X
authorships[0].author.display_name	Pankaj K. Agarwal
authorships[0].countries	US
authorships[0].affiliations[0].institution_ids	https://openalex.org/I170897317
authorships[0].affiliations[0].raw_affiliation_string	Duke University [Durham] (Durham, NC 27708 - United States)
authorships[0].institutions[0].id	https://openalex.org/I170897317
authorships[0].institutions[0].ror	https://ror.org/00py81415
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I170897317
authorships[0].institutions[0].country_code	US
authorships[0].institutions[0].display_name	Duke University
authorships[0].author_position	first
authorships[0].raw_author_name	Pankaj K. Agarwal
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Duke University [Durham] (Durham, NC 27708 - United States)
authorships[1].author.id	https://openalex.org/A5042232059
authorships[1].author.orcid	https://orcid.org/0000-0003-3110-4702
authorships[1].author.display_name	Boris Aronov
authorships[1].countries	US
authorships[1].affiliations[0].institution_ids	https://openalex.org/I4210128391
authorships[1].affiliations[0].raw_affiliation_string	NYU Tandon School of Engineering (6 MetroTech Center, Brooklyn, NY 11201 - United States)
authorships[1].institutions[0].id	https://openalex.org/I4210128391
authorships[1].institutions[0].ror	https://ror.org/02qk65b13
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I4210128391
authorships[1].institutions[0].country_code	US
authorships[1].institutions[0].display_name	Brooklyn Technical High School
authorships[1].author_position	middle
authorships[1].raw_author_name	Boris Aronov
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	NYU Tandon School of Engineering (6 MetroTech Center, Brooklyn, NY 11201 - United States)
authorships[2].author.id	https://openalex.org/A5111488193
authorships[2].author.orcid
authorships[2].author.display_name	Guillaume Moroz
authorships[2].affiliations[0].raw_affiliation_string	GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm (615 rue du Jardin Botanique 54600 Villers-lès-Nancy - France)
authorships[2].author_position	last
authorships[2].raw_author_name	Guillaume Moroz
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm (615 rue du Jardin Botanique 54600 Villers-lès-Nancy - France)
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://hal.science/hal-04908634
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	A Subquadratic Algorithm for Computing the L₁-Distance Between Two Terrains
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10996
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.5371999740600586
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1704
primary_topic.subfield.display_name	Computer Graphics and Computer-Aided Design
primary_topic.display_name	Computational Geometry and Mesh Generation
related_works	https://openalex.org/W4391375266, https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W4399671601, https://openalex.org/W1992962589, https://openalex.org/W2051487156, https://openalex.org/W3032871857, https://openalex.org/W1743191351, https://openalex.org/W3104633800, https://openalex.org/W2069184433
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:HAL:hal-04908634v1
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306402512
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	HAL (Le Centre pour la Communication Scientifique Directe)
best_oa_location.source.host_organization	https://openalex.org/I1294671590
best_oa_location.source.host_organization_name	Centre National de la Recherche Scientifique
best_oa_location.source.host_organization_lineage	https://openalex.org/I1294671590
best_oa_location.license	other-oa
best_oa_location.pdf_url
best_oa_location.version	submittedVersion
best_oa_location.raw_type	Conference papers
best_oa_location.license_id	https://openalex.org/licenses/other-oa
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name	Symposium on Computational Geometry (SoCG), Jun 2025, Kanazawa, Japan. pp.4:1-4:17, ⟨10.4230/LIPIcs.SoCG.2025.4⟩
best_oa_location.landing_page_url	https://hal.science/hal-04908634
primary_location.id	pmh:oai:HAL:hal-04908634v1
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306402512
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	False
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	HAL (Le Centre pour la Communication Scientifique Directe)
primary_location.source.host_organization	https://openalex.org/I1294671590
primary_location.source.host_organization_name	Centre National de la Recherche Scientifique
primary_location.source.host_organization_lineage	https://openalex.org/I1294671590
primary_location.license	other-oa
primary_location.pdf_url
primary_location.version	submittedVersion
primary_location.raw_type	Conference papers
primary_location.license_id	https://openalex.org/licenses/other-oa
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name	Symposium on Computational Geometry (SoCG), Jun 2025, Kanazawa, Japan. pp.4:1-4:17, ⟨10.4230/LIPIcs.SoCG.2025.4⟩
primary_location.landing_page_url	https://hal.science/hal-04908634
publication_date	2025-01-01
publication_year	2025
referenced_works_count	0
abstract_inverted_index.=	31, 71
abstract_inverted_index.>	92
abstract_inverted_index.a	18, 54
abstract_inverted_index.f	13, 37
abstract_inverted_index.g	39
abstract_inverted_index.n	57
abstract_inverted_index.0.	93
abstract_inverted_index.If	36
abstract_inverted_index.We	0
abstract_inverted_index.be	64
abstract_inverted_index.by	42
abstract_inverted_index.dx	34
abstract_inverted_index.g,	15
abstract_inverted_index.if	111
abstract_inverted_index.in	66
abstract_inverted_index.is	75, 106, 121, 129
abstract_inverted_index.of	4, 51, 56, 85, 103, 114, 117, 126
abstract_inverted_index.we	59
abstract_inverted_index.Õ	81
abstract_inverted_index.α	70
abstract_inverted_index.ε	91
abstract_inverted_index.ω	74
abstract_inverted_index.and	14, 38, 48, 80, 119
abstract_inverted_index.any	90
abstract_inverted_index.are	40
abstract_inverted_index.can	63
abstract_inverted_index.dy.	35
abstract_inverted_index.for	89, 97
abstract_inverted_index.is,	26
abstract_inverted_index.our	127
abstract_inverted_index.the	2, 6, 28, 76, 86, 98, 112, 115, 124
abstract_inverted_index.two	9
abstract_inverted_index.κ,	122
abstract_inverted_index.ω,	104
abstract_inverted_index.⊂	23
abstract_inverted_index.More	109
abstract_inverted_index.This	94
abstract_inverted_index.best	100
abstract_inverted_index.form	87
abstract_inverted_index.n^ε	88
abstract_inverted_index.over	17, 45
abstract_inverted_index.show	60
abstract_inverted_index.that	25, 61
abstract_inverted_index.then	123
abstract_inverted_index.with	53
abstract_inverted_index.𝕄	22, 52
abstract_inverted_index.2.37.	108
abstract_inverted_index.8/5},	73
abstract_inverted_index.bound	95
abstract_inverted_index.hides	83
abstract_inverted_index.holds	96
abstract_inverted_index.known	101
abstract_inverted_index.study	1
abstract_inverted_index.time,	68
abstract_inverted_index.total	55
abstract_inverted_index.value	102
abstract_inverted_index.where	69
abstract_inverted_index.which	105
abstract_inverted_index.domain	21
abstract_inverted_index.linear	43
abstract_inverted_index.matrix	77
abstract_inverted_index.ℝ²,	24
abstract_inverted_index.𝐓_f	47, 118
abstract_inverted_index.𝐓_g	120
abstract_inverted_index.between	8
abstract_inverted_index.bounded	19
abstract_inverted_index.defined	16, 41
abstract_inverted_index.factors	84
abstract_inverted_index.overlay	116
abstract_inverted_index.problem	3
abstract_inverted_index.runtime	125
abstract_inverted_index.𝐓_g,	49
abstract_inverted_index.computed	65
abstract_inverted_index.notation	82
abstract_inverted_index.quantity	29
abstract_inverted_index.Õ(n^α)	67
abstract_inverted_index.∫_𝕄	32
abstract_inverted_index.algorithm	128
abstract_inverted_index.bivariate	11
abstract_inverted_index.computing	5, 27
abstract_inverted_index.currently	99
abstract_inverted_index.exponent,	79
abstract_inverted_index.functions	12
abstract_inverted_index.polygonal	20
abstract_inverted_index.complexity	113
abstract_inverted_index.generally,	110
abstract_inverted_index.triangles,	58
abstract_inverted_index.‖f-g‖₁	30, 62
abstract_inverted_index.L₁-distance	7
abstract_inverted_index.approximately	107
abstract_inverted_index.interpolation	44
abstract_inverted_index.max{(ω+1)/2,	72
abstract_inverted_index.respectively,	50
abstract_inverted_index.multiplication	78
abstract_inverted_index.triangulations	46
abstract_inverted_index.\|f(x,y)-g(x,y)\|	33
abstract_inverted_index.piecewise-linear	10
abstract_inverted_index.Õ(κ^{α-1}n^{2-α}).	130
cited_by_percentile_year
countries_distinct_count	1
institutions_distinct_count	3
citation_normalized_percentile.value	0.02777267
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True