Computing shortest paths amid non-overlapping weighted disks Article Swipe
Prosenjit Bose
,
Jean-Lou De Carufel
,
Guillermo Esteban
,
Anil Maheshwari
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2409.08869
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2409.08869
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
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2409.08869
- https://arxiv.org/pdf/2409.08869
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4403662181
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4403662181Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2409.08869Digital Object Identifier
- Title
-
Computing shortest paths amid non-overlapping weighted disksWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-09-13Full publication date if available
- Authors
-
Prosenjit Bose, Jean-Lou De Carufel, Guillermo Esteban, Anil MaheshwariList of authors in order
- Landing page
-
https://arxiv.org/abs/2409.08869Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2409.08869Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2409.08869Direct OA link when available
- Concepts
-
Computer science, AlgorithmTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4403662181 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2409.08869 |
| ids.doi | https://doi.org/10.48550/arxiv.2409.08869 |
| ids.openalex | https://openalex.org/W4403662181 |
| fwci | |
| type | preprint |
| title | Computing shortest paths amid non-overlapping weighted disks |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11106 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9623000025749207 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1711 |
| topics[0].subfield.display_name | Signal Processing |
| topics[0].display_name | Data Management and Algorithms |
| 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.9419999718666077 |
| 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/T11063 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9110000133514404 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1703 |
| topics[2].subfield.display_name | Computational Theory and Mathematics |
| topics[2].display_name | Rough Sets and Fuzzy Logic |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.5453989505767822 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C11413529 |
| concepts[1].level | 1 |
| concepts[1].score | 0.32505106925964355 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[1].display_name | Algorithm |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.5453989505767822 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/algorithm |
| keywords[1].score | 0.32505106925964355 |
| keywords[1].display_name | Algorithm |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2409.08869 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2409.08869 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2409.08869 |
| locations[1].id | doi:10.48550/arxiv.2409.08869 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2409.08869 |
| indexed_in | arxiv, datacite |
| 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 | Bose, Prosenjit |
| 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 | De Carufel, Jean-Lou |
| 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 | Esteban, Guillermo |
| 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 | Maheshwari, Anil |
| 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://arxiv.org/pdf/2409.08869 |
| open_access.oa_status | green |
| 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-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11106 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9623000025749207 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1711 |
| primary_topic.subfield.display_name | Signal Processing |
| primary_topic.display_name | Data Management and Algorithms |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W2051487156, https://openalex.org/W2073681303, https://openalex.org/W2390279801, https://openalex.org/W4391913857, https://openalex.org/W2358668433, https://openalex.org/W4396701345, https://openalex.org/W2376932109 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2409.08869 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| 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 | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2409.08869 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2409.08869 |
| primary_location.id | pmh:oai:arXiv.org:2409.08869 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2409.08869 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2409.08869 |
| publication_date | 2024-09-13 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.$ | 18, 20, 31, 44, 47 |
| abstract_inverted_index.a | 15, 28, 79, 88 |
| abstract_inverted_index.n | 19 |
| abstract_inverted_index.(1 | 45 |
| abstract_inverted_index.In | 0 |
| abstract_inverted_index.an | 5 |
| abstract_inverted_index.at | 42 |
| abstract_inverted_index.by | 68 |
| abstract_inverted_index.in | 24, 91, 96 |
| abstract_inverted_index.is | 41, 60 |
| abstract_inverted_index.of | 17, 37, 53, 65, 74 |
| abstract_inverted_index.on | 62, 71 |
| abstract_inverted_index.we | 3, 81 |
| abstract_inverted_index.For | 27 |
| abstract_inverted_index.The | 58 |
| abstract_inverted_index.\in | 33 |
| abstract_inverted_index.can | 82 |
| abstract_inverted_index.for | 8, 86 |
| abstract_inverted_index.set | 16 |
| abstract_inverted_index.the | 10, 25, 35, 38, 51, 54, 63, 66, 72, 75, 92 |
| abstract_inverted_index.use | 83 |
| abstract_inverted_index.most | 43 |
| abstract_inverted_index.path | 40, 90 |
| abstract_inverted_index.such | 78 |
| abstract_inverted_index.than | 50 |
| abstract_inverted_index.this | 1 |
| abstract_inverted_index.Using | 77 |
| abstract_inverted_index.based | 61 |
| abstract_inverted_index.disks | 23 |
| abstract_inverted_index.given | 29 |
| abstract_inverted_index.graph | 94 |
| abstract_inverted_index.path. | 57 |
| abstract_inverted_index.space | 67 |
| abstract_inverted_index.time. | 98 |
| abstract_inverted_index.times | 48 |
| abstract_inverted_index.Region | 12 |
| abstract_inverted_index.actual | 55 |
| abstract_inverted_index.amidst | 14 |
| abstract_inverted_index.disks. | 76 |
| abstract_inverted_index.larger | 49 |
| abstract_inverted_index.length | 36, 52 |
| abstract_inverted_index.plane. | 26 |
| abstract_inverted_index.points | 70 |
| abstract_inverted_index.(0,1]$, | 34 |
| abstract_inverted_index.Problem | 13 |
| abstract_inverted_index.placing | 69 |
| abstract_inverted_index.present | 4 |
| abstract_inverted_index.solving | 9 |
| abstract_inverted_index.Weighted | 11 |
| abstract_inverted_index.article, | 2 |
| abstract_inverted_index.boundary | 73 |
| abstract_inverted_index.obtained | 95 |
| abstract_inverted_index.shortest | 56, 89 |
| abstract_inverted_index.weighted | 22 |
| abstract_inverted_index.algorithm | 7, 59, 85 |
| abstract_inverted_index.computing | 87 |
| abstract_inverted_index.geometric | 93 |
| abstract_inverted_index.parameter | 30 |
| abstract_inverted_index.Dijkstra's | 84 |
| abstract_inverted_index.\varepsilon | 32 |
| abstract_inverted_index.approximate | 39 |
| abstract_inverted_index.+\varepsilon) | 46 |
| abstract_inverted_index.approximation | 6 |
| abstract_inverted_index.discretization | 64, 80 |
| abstract_inverted_index.non-overlapping | 21 |
| abstract_inverted_index.(pseudo-)polynomial | 97 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile |