Computing Shortest Paths Amid Non-overlapping Weighted Disks Article Swipe

View

Prosenjit Bose , Jean-Lou De Carufel , Guillermo Esteban , Anil Maheshwari ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.1007/s00025-025-02479-2

In this article, we present an approximation algorithm for solving the Weighted Region Problem amidst a set of n non-overlapping weighted disks in the plane. For a given parameter $$ \varepsilon \in (0,1]$$ , the length of the approximate path is at most $$ (1 +\varepsilon ) $$ times larger than the length of the actual shortest path. The algorithm is based on the discretization of the space by placing points on the boundary of the disks. Using such a discretization we can use Dijkstra’s algorithm for computing a shortest path in the geometric graph obtained in (pseudo-)polynomial time.

Related Topics

Concepts

Algorithm Dijkstra's algorithm Shortest path problem Computer science Mathematics Graph Combinatorics

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.1007/s00025-025-02479-2
OA Status: hybrid
References: 37
Related Works: 10
OpenAlex ID: https://openalex.org/W4412967130

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1007/s00025-025-02479-2

Digital Object Identifier
Title: Computing Shortest Paths Amid Non-overlapping Weighted Disks

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-07-19

Full publication date if available
Authors: Prosenjit Bose, Jean-Lou De Carufel, Guillermo Esteban, Anil Maheshwari

List of authors in order
Landing page: https://doi.org/10.1007/s00025-025-02479-2

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: hybrid

Open access status per OpenAlex
OA URL: https://doi.org/10.1007/s00025-025-02479-2

Direct OA link when available
Concepts: Algorithm, Dijkstra's algorithm, Shortest path problem, Computer science, Mathematics, Graph, Combinatorics

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

Total citation count in OpenAlex
References (count): 37

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4412967130
doi	https://doi.org/10.1007/s00025-025-02479-2
ids.doi	https://doi.org/10.1007/s00025-025-02479-2
ids.openalex	https://openalex.org/W4412967130
fwci	0.0
type	article
title	Computing Shortest Paths Amid Non-overlapping Weighted Disks
awards[0].id	https://openalex.org/G8349410577
awards[0].funder_id	https://openalex.org/F4320315062
awards[0].display_name
awards[0].funder_award_id	PID2019-104129GB-I00
awards[0].funder_display_name	Ministerio de Ciencia, Innovación y Universidades
awards[1].id	https://openalex.org/G7134128730
awards[1].funder_id	https://openalex.org/F4320323755
awards[1].display_name
awards[1].funder_award_id	PID2023-150725NB-I00
awards[1].funder_display_name	Universidad de Alcalá
biblio.issue	5
biblio.volume	80
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.9990000128746033
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
topics[1].id	https://openalex.org/T11245
topics[1].field.id	https://openalex.org/fields/22
topics[1].field.display_name	Engineering
topics[1].score	0.9896000027656555
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2206
topics[1].subfield.display_name	Computational Mechanics
topics[1].display_name	Advanced Numerical Analysis Techniques
topics[2].id	https://openalex.org/T12176
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.9578999876976013
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2209
topics[2].subfield.display_name	Industrial and Manufacturing Engineering
topics[2].display_name	Optimization and Packing Problems
funders[0].id	https://openalex.org/F4320315062
funders[0].ror
funders[0].display_name	Ministerio de Ciencia, Innovación y Universidades
funders[1].id	https://openalex.org/F4320323755
funders[1].ror	https://ror.org/04pmn0e78
funders[1].display_name	Universidad de Alcalá
funders[2].id	https://openalex.org/F4320334593
funders[2].ror	https://ror.org/01h531d29
funders[2].display_name	Natural Sciences and Engineering Research Council of Canada
is_xpac	False
apc_list.value	2290
apc_list.currency	EUR
apc_list.value_usd	2890
apc_paid.value	2290
apc_paid.currency	EUR
apc_paid.value_usd	2890
concepts[0].id	https://openalex.org/C11413529
concepts[0].level	1
concepts[0].score	0.650898814201355
concepts[0].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[0].display_name	Algorithm
concepts[1].id	https://openalex.org/C173870130
concepts[1].level	4
concepts[1].score	0.5744062066078186
concepts[1].wikidata	https://www.wikidata.org/wiki/Q8548
concepts[1].display_name	Dijkstra's algorithm
concepts[2].id	https://openalex.org/C22590252
concepts[2].level	3
concepts[2].score	0.4642966389656067
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1058754
concepts[2].display_name	Shortest path problem
concepts[3].id	https://openalex.org/C41008148
concepts[3].level	0
concepts[3].score	0.4038795530796051
concepts[3].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[3].display_name	Computer science
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.35478928685188293
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C132525143
concepts[5].level	2
concepts[5].score	0.2960827052593231
concepts[5].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[5].display_name	Graph
concepts[6].id	https://openalex.org/C114614502
concepts[6].level	1
concepts[6].score	0.20284521579742432
concepts[6].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[6].display_name	Combinatorics
keywords[0].id	https://openalex.org/keywords/algorithm
keywords[0].score	0.650898814201355
keywords[0].display_name	Algorithm
keywords[1].id	https://openalex.org/keywords/dijkstras-algorithm
keywords[1].score	0.5744062066078186
keywords[1].display_name	Dijkstra's algorithm
keywords[2].id	https://openalex.org/keywords/shortest-path-problem
keywords[2].score	0.4642966389656067
keywords[2].display_name	Shortest path problem
keywords[3].id	https://openalex.org/keywords/computer-science
keywords[3].score	0.4038795530796051
keywords[3].display_name	Computer science
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.35478928685188293
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/graph
keywords[5].score	0.2960827052593231
keywords[5].display_name	Graph
keywords[6].id	https://openalex.org/keywords/combinatorics
keywords[6].score	0.20284521579742432
keywords[6].display_name	Combinatorics
language	en
locations[0].id	doi:10.1007/s00025-025-02479-2
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S939935174
locations[0].source.issn	1420-9012, 1422-6383
locations[0].source.type	journal
locations[0].source.is_oa	False
locations[0].source.issn_l	1420-9012
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Results in Mathematics
locations[0].source.host_organization	https://openalex.org/P4310320186
locations[0].source.host_organization_name	Birkhäuser
locations[0].source.host_organization_lineage	https://openalex.org/P4310320186, https://openalex.org/P4310319900
locations[0].source.host_organization_lineage_names	Birkhäuser, Springer Science+Business Media
locations[0].license	cc-by
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Results in Mathematics
locations[0].landing_page_url	https://doi.org/10.1007/s00025-025-02479-2
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5013674788
authorships[0].author.orcid	https://orcid.org/0000-0002-8906-0573
authorships[0].author.display_name	Prosenjit Bose
authorships[0].author_position	first
authorships[0].raw_author_name	Prosenjit Bose
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5042440491
authorships[1].author.orcid	https://orcid.org/0000-0002-6734-8234
authorships[1].author.display_name	Jean-Lou De Carufel
authorships[1].author_position	middle
authorships[1].raw_author_name	Jean-Lou De Carufel
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5059562219
authorships[2].author.orcid	https://orcid.org/0000-0002-0751-7729
authorships[2].author.display_name	Guillermo Esteban
authorships[2].author_position	middle
authorships[2].raw_author_name	Guillermo Esteban
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5103136561
authorships[3].author.orcid	https://orcid.org/0000-0002-1274-4598
authorships[3].author.display_name	Anil Maheshwari
authorships[3].author_position	last
authorships[3].raw_author_name	Anil Maheshwari
authorships[3].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://doi.org/10.1007/s00025-025-02479-2
open_access.oa_status	hybrid
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Computing Shortest Paths Amid Non-overlapping Weighted Disks
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
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.9990000128746033
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/W3209137076, https://openalex.org/W2374560440, https://openalex.org/W1490490684, https://openalex.org/W4221129498, https://openalex.org/W2887026015, https://openalex.org/W2375280931, https://openalex.org/W2361442013, https://openalex.org/W2373384475, https://openalex.org/W4310124294
cited_by_count	0
locations_count	1
best_oa_location.id	doi:10.1007/s00025-025-02479-2
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S939935174
best_oa_location.source.issn	1420-9012, 1422-6383
best_oa_location.source.type	journal
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l	1420-9012
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Results in Mathematics
best_oa_location.source.host_organization	https://openalex.org/P4310320186
best_oa_location.source.host_organization_name	Birkhäuser
best_oa_location.source.host_organization_lineage	https://openalex.org/P4310320186, https://openalex.org/P4310319900
best_oa_location.source.host_organization_lineage_names	Birkhäuser, Springer Science+Business Media
best_oa_location.license	cc-by
best_oa_location.pdf_url
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Results in Mathematics
best_oa_location.landing_page_url	https://doi.org/10.1007/s00025-025-02479-2
primary_location.id	doi:10.1007/s00025-025-02479-2
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S939935174
primary_location.source.issn	1420-9012, 1422-6383
primary_location.source.type	journal
primary_location.source.is_oa	False
primary_location.source.issn_l	1420-9012
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Results in Mathematics
primary_location.source.host_organization	https://openalex.org/P4310320186
primary_location.source.host_organization_name	Birkhäuser
primary_location.source.host_organization_lineage	https://openalex.org/P4310320186, https://openalex.org/P4310319900
primary_location.source.host_organization_lineage_names	Birkhäuser, Springer Science+Business Media
primary_location.license	cc-by
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Results in Mathematics
primary_location.landing_page_url	https://doi.org/10.1007/s00025-025-02479-2
publication_date	2025-07-19
publication_year	2025
referenced_works	https://openalex.org/W111486705, https://openalex.org/W1980197133, https://openalex.org/W2028769163, https://openalex.org/W1902053630, https://openalex.org/W4395053204, https://openalex.org/W2006095056, https://openalex.org/W2010963977, https://openalex.org/W1994987092, https://openalex.org/W1983422667, https://openalex.org/W2565603695, https://openalex.org/W2077163943, https://openalex.org/W2052206570, https://openalex.org/W2012691739, https://openalex.org/W81474395, https://openalex.org/W2040904149, https://openalex.org/W2023618719, https://openalex.org/W2495937958, https://openalex.org/W1725324094, https://openalex.org/W2077159475, https://openalex.org/W2058510050, https://openalex.org/W4293052584, https://openalex.org/W1845390921, https://openalex.org/W2048095461, https://openalex.org/W1534329287, https://openalex.org/W1989723858, https://openalex.org/W1505970908, https://openalex.org/W2030533649, https://openalex.org/W2011380591, https://openalex.org/W2040638477, https://openalex.org/W2100185791, https://openalex.org/W1994286847, https://openalex.org/W2050710547, https://openalex.org/W2066528300, https://openalex.org/W3040601751, https://openalex.org/W2112346596, https://openalex.org/W1589443075, https://openalex.org/W2031671531
referenced_works_count	37
abstract_inverted_index.)	59
abstract_inverted_index.,	46
abstract_inverted_index.a	16, 27, 102, 111
abstract_inverted_index.n	19
abstract_inverted_index.$$	30, 56, 60
abstract_inverted_index.(1	57
abstract_inverted_index.In	1
abstract_inverted_index.an	6
abstract_inverted_index.at	54
abstract_inverted_index.by	91
abstract_inverted_index.in	23, 114, 119
abstract_inverted_index.is	53, 83
abstract_inverted_index.of	18, 49, 76, 88, 97
abstract_inverted_index.on	85, 94
abstract_inverted_index.we	4, 104
abstract_inverted_index.For	26
abstract_inverted_index.The	81
abstract_inverted_index.\in	32
abstract_inverted_index.can	105
abstract_inverted_index.for	9, 109
abstract_inverted_index.set	17
abstract_inverted_index.the	11, 24, 47, 50, 74, 77, 86, 89, 95, 98, 115
abstract_inverted_index.use	106
abstract_inverted_index.most	55
abstract_inverted_index.path	52, 113
abstract_inverted_index.such	101
abstract_inverted_index.than	73
abstract_inverted_index.this	2
abstract_inverted_index.Using	100
abstract_inverted_index.based	84
abstract_inverted_index.disks	22
abstract_inverted_index.given	28
abstract_inverted_index.graph	117
abstract_inverted_index.path.	80
abstract_inverted_index.space	90
abstract_inverted_index.time.	121
abstract_inverted_index.times	71
abstract_inverted_index.Region	13
abstract_inverted_index.actual	78
abstract_inverted_index.amidst	15
abstract_inverted_index.disks.	99
abstract_inverted_index.larger	72
abstract_inverted_index.length	48, 75
abstract_inverted_index.plane.	25
abstract_inverted_index.points	93
abstract_inverted_index.(0,1]$$	33
abstract_inverted_index.Problem	14
abstract_inverted_index.placing	92
abstract_inverted_index.present	5
abstract_inverted_index.solving	10
abstract_inverted_index.Abstract	0
abstract_inverted_index.Weighted	12
abstract_inverted_index.article,	3
abstract_inverted_index.boundary	96
abstract_inverted_index.obtained	118
abstract_inverted_index.shortest	79, 112
abstract_inverted_index.weighted	21
abstract_inverted_index.<mml:math	34, 61
abstract_inverted_index.algorithm	8, 82, 108
abstract_inverted_index.computing	110
abstract_inverted_index.geometric	116
abstract_inverted_index.parameter	29
abstract_inverted_index.<mml:mrow>	36, 63
abstract_inverted_index.</mml:math>	45, 70
abstract_inverted_index.</mml:mrow>	44, 69
abstract_inverted_index.\varepsilon	31
abstract_inverted_index.approximate	51
abstract_inverted_index.+\varepsilon	58
abstract_inverted_index.Dijkstra’s	107
abstract_inverted_index.approximation	7
abstract_inverted_index.discretization	87, 103
abstract_inverted_index.non-overlapping	20
abstract_inverted_index.<mml:mn>0</mml:mn>	40
abstract_inverted_index.<mml:mn>1</mml:mn>	42, 65
abstract_inverted_index.<mml:mo>(</mml:mo>	39, 64
abstract_inverted_index.<mml:mo>)</mml:mo>	68
abstract_inverted_index.<mml:mo>+</mml:mo>	66
abstract_inverted_index.<mml:mo>,</mml:mo>	41
abstract_inverted_index.<mml:mo>]</mml:mo>	43
abstract_inverted_index.(pseudo-)polynomial	120
abstract_inverted_index.<mml:mi>ε</mml:mi>	37, 67
abstract_inverted_index.<mml:mo>∈</mml:mo>	38
abstract_inverted_index.xmlns:mml="http://www.w3.org/1998/Math/MathML">	35, 62
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile.value	0.46889171
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True