Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known: the equilateral triangle, the square, the regular hexagon and the rectangle. We add a fifth convex shape by proving the exact spanning ratio of the parallelogram Delaunay graph. The worst-case spanning ratio is exactly \( \frac{\sqrt{2}\sqrt{1+A^2+2A\cos (\theta _0)+(A+\cos (\theta _0))\sqrt{1+A^2+2A\cos (\theta _0)}}}{\sin (\theta _0)}, \) where A is the aspect ratio and \(\theta _0\) is the non-obtuse angle of the parallelogram.

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

The Exact Spanning Ratio of the Parallelogram Delaunay Graph

  • Prosenjit Bose,
  • Jean-Lou De Carufel,
  • Sandrine Njoo

摘要

Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known: the equilateral triangle, the square, the regular hexagon and the rectangle. We add a fifth convex shape by proving the exact spanning ratio of the parallelogram Delaunay graph. The worst-case spanning ratio is exactly \( \frac{\sqrt{2}\sqrt{1+A^2+2A\cos (\theta _0)+(A+\cos (\theta _0))\sqrt{1+A^2+2A\cos (\theta _0)}}}{\sin (\theta _0)}, \) where A is the aspect ratio and \(\theta _0\) is the non-obtuse angle of the parallelogram.