Евклидово минимальное остовное дерево

Евклидово минимальное остовное дерево (Euclidean minimum spanning tree, EMST) — это минимальное остовное дерево множества из [math]\displaystyle{ n }[/math] точек на плоскости (или более обще, в [math]\displaystyle{ \R^d }[/math], где [math]\displaystyle{ d \ge 2 }[/math]), где вес ребра между любой парой точек является евклидовым расстоянием между ними. Другими словами, Евклидово минимальное остовное дерево соединяет отрезками некоторые пары заданного множества из [math]\displaystyle{ n }[/math] точек так, что любая точка множества стала достижимой из любой другой точки множества по этим отрезкам, а общая длина всех отрезков была бы минимальна.