Как найти Евклидовое минимальное связующее дерево с использованием библиотеки CGAL?

Question

У меня есть набор двумерных точек, и, рассматривая каждую точку, связанную с каждым другим, с «ребром» с весом, равным расстоянию между ними, мне нужно найти MST полученного графа. Я использую тот факт, что EMST всегда является подграфом триангуляции delaunay этого поля. Мне нужны треугольники, как список ребер, чтобы сделать граф из него, а затем запустить Крускал над ним.

Кроме того, должен ли я идти по пути триангуляции Делоне или есть прямая функция для него?

Просьба предоставить образец кода для определения, какие заголовки включать, какое пространство имен использовать и т. Д. С вашим ответом для любого вопроса, если это возможно.

Answer 1

В 2D число ребер триангуляции является линейным. Как только триангуляция Delaunay вычисляется с использованием cgal, вы можете использовать реализацию минимального связующего дерева на графике. См. Страницу wikipedia Euclidean minimum spanning tree.