Scholarlink

<p>Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper, we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1308_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(A\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>A</mi> </math></EquationSource> </InlineEquation> have spanning ratio at most <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1308_Article_IEq2.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="186" /> </InlineMediaObject> <EquationSource Format="TEX">\(\sqrt{2} \sqrt{1+A^2 + A\sqrt{A^2 + 1}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msqrt> <mn>2</mn> </msqrt> <msqrt> <mrow> <mn>1</mn> <mo>+</mo> <msup> <mi>A</mi> <mn>2</mn> </msup> <mo>+</mo> <mi>A</mi> <msqrt> <mrow> <msup> <mi>A</mi> <mn>2</mn> </msup> <mo>+</mo> <mn>1</mn> </mrow> </msqrt> </mrow> </msqrt> </mrow> </math></EquationSource> </InlineEquation>, which matches the known lower bound.</p>

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

The Tight Spanning Ratio of the Rectangle Delaunay Triangulation

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年4月16日

查看全文
  • André van Renssen,
  • Yuan Sha,
  • Yucheng Sun,
  • Sampson Wong

摘要

Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper, we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio \(A\) A have spanning ratio at most \(\sqrt{2} \sqrt{1+A^2 + A\sqrt{A^2 + 1}}\) 2 1 + A 2 + A A 2 + 1 , which matches the known lower bound.