стандартные алгоритмы MST работают на графике. если вы начнете с набора вершин без какой-либо другой информации, кроме парных (абстрактных) расстояний между вершинами, ваш стандартный подход потребует от вас запустить алгоритм mst для всего графа с O(n^2) ребрами. так как сложность стандартных алгоритмов MST зависит от количества ребер (например, O(e log e) для Kruskal), было бы более эффективно, если бы вы могли сократить количество ребер в графе для начала - что относится к триангуляции Делоне. рассматривается как граф, поскольку он имеет ребра O(n) (я не буду обсуждать, что mst исходного набора точек является подмножеством графа Делоне, как вы это признаете).
Ваш исходный набор точек может быть подвержен другим ограничениям, которые либо препятствуют триангуляции Делоне (например, коллинеарным точкам), либо допускают начало еще более разреженного графа (например, выпуклой оболочки с минимальным диаметром, меньшим, чем минимальное расстояние). между двумя точками в вашем наборе точек).
С уважением, Карстен