algorithm - 二维集的稀疏性

Question

定义一组S元素(x,y)的稀疏性，x,y为实数，为最小实数d，满足对于 S 中的任何元素 v，以 v 为中心，半径为 的闭合穿孔球d, 是非空的(通过穿刺球，即不包括它的中心的球)。显然，如果 S 非空，这样的 d 存在，并且是唯一的。

找出给定集合的稀疏性。

显然，我们有朴素的二次时间解。

Answer 1

如果我理解正确，天真的解决方案是取距离每个点最近的点，答案是这些最小值中的最大值。

构建你的点的 MST(最小生成树)。 (形式上，也就是完全图的MST，点是顶点，边的权重是对应点之间的距离。)MST有一个性质:对于每个顶点，入射到它的最小边在MST中。因此，仅检查 MST 的边缘就足以找到答案。

构建一组点的 MST 的最快方法是在 Delaunay triangulation 处构建在它上面，然后使用 Kruskal's algorithm 找到它的 MST .这两个步骤都需要 O(n log n) 时间，这是算法的整体运行时间。

但是，构建 Delaunay 三角剖分相当复杂，因此请考虑搜索现有库而不是从头开始编码。