Прямолинейное остовное дерево: различия между версиями

Внимательное рассмотрение также позволяет прийти к выводу, что после заметания области <math>R_1 \;</math> нет необходимости в заметании <math>R_5 \;</math>, поскольку все ребра, необходимые на данном этапе, уже включены или предполагаются. Более того, основываясь на информации из <math>R_5 \;</math>, количество реберных соединений можно еще больше сократить. Во время обработки заметающим процессом точки s он находит подмножество активных точек, содержащих s в их областях <math>R_1 \;</math>. Без потери общности будем считать, что к ним относятся точки p и q. Тогда p и q принадлежат к области R5 точки s, что означает ||pq|| < max(||sp||; ||sq||). Следовательно, необходимо только соединить s с ближайшей активной точкой.