论文标题
矩形Delaunay三角剖分的紧密跨度
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
论文作者
论文摘要
Spanner构造是一个充分研究的问题，Delaunay三角剖分是最受欢迎的跨越。紧密的边界是使用等边三角形，正方形或常规六边形的delaunay三角剖分是否构建的。但是，所有其他形状仍然难以捉摸。在本文中，我们扩展了已知紧密界限的限制类别的跨度类别。我们证明，使用矩形构建具有长宽比$ a $具有跨度比的delaunay三角形，最多最多$ \ sqrt {2} \ sqrt {1 + a^2 + a^2 + a \ sqrt {a^2 + 1}} $，与已知的下限相匹配。
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$ have spanning ratio at most $\sqrt{2} \sqrt{1+A^2 + A \sqrt{A^2 + 1}}$, which matches the known lower bound.
