optimization - 斯坦纳树和完全图之间的图

Question

给定平面上的设定点 P 和阈值 t，我想计算一个连通图 G 以最小化其边的长度之和，但要遵守以下约束：

• G 的顶点包含 P 中的所有点。
• 对于 P 中的每一对点 u 和 v，它们在 G 中的距离不大于它们的欧几里得距离的 t 倍。

当 t=1 时，这个问题通过在 P 上构建一个完整的图来解决。当 t 是无限的（或者只是足够大）时，这个问题就是欧几里德斯坦纳树问题。

如果已经有这个问题的名称，我很好奇它是什么。不仅如此，有人对如何为此制定算法有任何建议吗？由于它包含作为特例的欧几里得斯坦纳树问题，所以它再简单不过了，所以我不是在寻找任何特别节省时间的东西。谢谢！

标签： optimizationgraphcomputational-geometry