Scholarlink

<p>In this article, we present an approximation algorithm for solving the Weighted Region Problem amidst a set of <i>n</i> non-overlapping weighted disks in the plane. For a given parameter <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="25_2025_2479_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="64" /> </InlineMediaObject> <EquationSource Format="TEX">\( \varepsilon \in (0,1]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>, the length of the approximate path is at most <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="25_2025_2479_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\( (1 +\varepsilon ) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>ε</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Computing Shortest Paths Amid Non-overlapping Weighted Disks

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年7月19日

查看全文
  • Prosenjit Bose,
  • Jean-Lou De Carufel,
  • Guillermo Esteban,
  • Anil Maheshwari

摘要

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]\) ε ∈ ( 0 , 1 ] , the length of the approximate path is at most \( (1 +\varepsilon ) \) ( 1 + ε ) 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.