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

Для сокращения количества потенциальных пар «точка-ребро» с <math>O(n^2) \;</math> до <math>O(n) \;</math> Бора и коллеги предложили использовать параметр видимости точки со стороны ребра: только точка, видимая от ребра, может рассматриваться для подключения к нему. Для поиска отношений видимости между точками и ребрами необходим заметающий алгоритм. Чтобы избежать выполнения этого сложного этапа, используется информация о геометрической близости, встроенная в остовный граф. Поскольку у точки имеется восемь ближайших точек, подключенных вблизи нее, то можно заметить: если точка видима от ребра, то она обычно подключена в графе по меньшей мере к одной из конечных точек ребра. Алгоритм использует остовный граф для генерации пар-кандидатов «точка-ребро». Для каждого ребра текущего дерева все точки, являющиеся соседями одной из конечных точек ребра, будут рассматриваться в качестве потенциальных пар. Поскольку мощность остовного графа составляет O(n), количество возможных пар, сгенерированных таким образом, также укладывается в эту оценку.