4551
правка
Прямолинейное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
м
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 11:34, 28 апреля 2016
, 28 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 48: | Строка 48: | ||
[[Файл:RST_1.png]] | [[Файл:RST_1.png]] | ||
Рис. 1. Восьмиугольное разбиение и свойство единственности | Рис. 1. Восьмиугольное разбиение и свойство единственности. | ||
| Строка 78: | Строка 78: | ||
for (i = 0; i < 2; i + +) { | '''for''' (i = 0; i < 2; i + +) { | ||
if (i == 0) отсортировать точки согласно x + y; | '''if''' (i == 0) отсортировать точки согласно x + y; | ||
else отсортировать точки согласно x - y; | '''else''' отсортировать точки согласно x - y; | ||
A[l] = A[2] = <math>\empty</math> | A[l] = A[2] = <math>\empty</math> | ||
'''for''' каждой точки согласно порядку { | |||
найти точки в А[1], А[2], такие, что p находится в их областях <math>R_{2i+1}</math> и <math>R_{2i+2}</math>, соответственно; | найти точки в А[1], А[2], такие, что p находится в их областях <math>R_{2i+1}</math> и <math>R_{2i+2}</math>, соответственно; | ||
соединить p с ближайшей точкой каждого подмножества; | соединить p с ближайшей точкой каждого подмножества; | ||
| Строка 89: | Строка 90: | ||
} | } | ||
Рис. 2. Алгоритм вычисления прямолинейного остовного графа | Рис. 2. Алгоритм вычисления прямолинейного остовного графа. | ||
| Строка 95: | Строка 96: | ||
Теорема 3. Пусть имеется n точек на плоскости. Алгоритм вычисления прямолинейного остовного графа строит остовный граф за время O(n log n), при этом количество ребер графа составляет O(n). | '''Теорема 3. Пусть имеется n точек на плоскости. Алгоритм вычисления прямолинейного остовного графа строит остовный граф за время O(n log n), при этом количество ребер графа составляет O(n).''' | ||