algorithm - 在 (x,y) 点的集合上生成图形

Question

问题:

给定平面中的一组二维点，找到一组边E，使任意两点之间的平均行程时间和E的大小最小化:即，通过将成本 r 与每个行程时间单位和集合中每个边的成本 e 相关联。

我确信有一组算法可以解决这个问题，但我似乎找不到合适的搜索词。我考虑过从完整的图形开始并进行修剪，但我想不出一种有效的方法来计算通过删除边缘造成的损害。有什么建议么？欢迎提供近似(“足够好”)的解决方案。

如果我对问题的陈述可以改进或澄清，请告诉我。

Answer 1

关于 spanners 的文献中有一些工作，这与您所描述的内容有关(主要区别在于 Spanner 控制最大拉伸(stretch)，而您关注的是平均值)。 Chew 的构造(“有一个平面图几乎和完整的图一样好”，SoCG '86)为您的问题提供了 O(1) 近似值，因为三角剖分的边数不到生成树的边数的三倍(最优值的下限，因为图必须是连通的)并调整每个欧几里德距离最多为 sqrt(10) 的一个因子(因此 sqrt(10) 乘以最优值的平均值)。