20万节点的Minimum Spanning Tree构建：Delaunay可靠性及替代方案咨询

我有一组约200000个代表城市经纬度的节点，需要计算其最小生成树（Minimum Spanning Tree）。我知道需要使用Prim算法，但首先要构建连通图（可假设节点处于欧几里得平面）。

最初考虑构建完全图，但205000*(205000-1)/2约为190亿条边，完全无法处理。

随后了解到Delaunay三角剖分：根据维基百科关于二维欧几里得最小生成树的相关内容，构建的Delaunay图包含最小生成树的子图，边数最多为3n-6，约600000条边，是MST算法的良好起点。

另一种方案是构建近似连通图，但可能遗漏影响MST结果的重要边。

Delaunay三角剖分在此场景下是否为可靠解决方案？若是，还有哪些可靠替代方案？

补充信息：该问题需用C语言实现。

已通过Delaunay三角剖分成功解决，相关代码可参考我的项目仓库。
注：部分代码较为粗糙，请注意。

内容的提问来源于stack exchange，提问作者aaalloc