Алгоритм Фортуны - Википедия - Fortunes algorithm

Анимация алгоритма фортуны

Алгоритм фортуны это алгоритм линии развертки для создания Диаграмма Вороного из набора точек на плоскости с помощью О (п бревноп) время и O (п) Космос.[1][2] Первоначально он был опубликован Стивен Форчун в 1986 г. в своей статье «Алгоритм Sweepline для диаграмм Вороного».[3]

Описание алгоритма

Алгоритм поддерживает как линия развертки и пляжная линия, которые оба перемещаются через плоскость по мере выполнения алгоритма. Линия развертки - это прямая линия, которую мы можем условно принять вертикальной и движущейся слева направо по плоскости. В любое время в ходе алгоритма входные точки слева от линии развертки будут включены в диаграмму Вороного, а точки справа от линии развертки еще не будут учитываться. Пляжная полоса не прямая, а сложная, кусочно кривая слева от линии сдвига, состоящая из частей параболы; он отделяет часть плоскости, в которой диаграмма Вороного может быть известна, независимо от того, какие другие точки могут быть справа от линии сдвига, от остальной части плоскости. Для каждой точки слева от линии сдвига можно определить параболу точек, равноудаленных от этой точки и от линии сдвига; пляжная линия является границей объединения этих парабол. По мере того, как линия развертки продвигается, вершины береговой линии, в которых пересекаются две параболы, очерчивают края диаграммы Вороного. Линия пляжа продвигается, удерживая каждое основание параболы точно на полпути между точками, первоначально охваченными линией сдвига, и новым положением линии сдвига. Математически это означает, что каждая парабола формируется с использованием линии качания в качестве директриса и точка ввода в качестве фокуса.

Алгоритм поддерживает как структуры данных двоичное дерево поиска описывающая комбинаторную структуру береговой линии, и приоритетная очередь перечисление потенциальных будущих событий, которые могут изменить структуру береговой линии. Эти события включают добавление другой параболы к линии пляжа (когда линия сдвига пересекает другую входную точку) и удаление кривой с линии пляжа (когда линия сдвига становится касательной к окружности через некоторые три входные точки, параболы которых образуют последовательные отрезки береговой линии). Каждому такому событию может быть присвоен приоритет Икс-координата линии развертки в точке, где произошло событие. Затем сам алгоритм состоит из многократного удаления следующего события из очереди приоритетов, поиска изменений, вызванных событием в береговой линии, и обновления структур данных.

Поскольку есть O (п) событий для обработки (каждое из которых связано с какой-либо функцией диаграммы Вороного) и O (журнал п) время обработки события (каждое из которых состоит из постоянного числа операций двоичного дерева поиска и приоритетной очереди), общее время составляет O (п бревно п).

Псевдокод

Псевдокод описание алгоритма.[4]

позволять  быть преобразованием ,  куда  это евклидово расстояние между z и ближайший сайт Т быть "пляжной полосой" пусть  быть регионом, охватываемым сайтом п.позволять  быть лучом границы между сайтами п и q.позволять  быть сайтами с минимальным у-координат, заказанный Икс-координатсоздать начальные вертикальные граничные лучи в то время как не Пусто(Q) делать    п ← DeleteMin (Q)    дело п из п это сайт в : найти вхождение региона  в Т содержащий п, заключенный в скобки  слева и  справа создать новые граничные лучи  и  с базами п        заменять  с  в Т        удалить из Q любое пересечение между  и         вставить в Q любое пересечение между  и         вставить в Q любое пересечение между  и     п является вершиной Вороного в :        позволять п быть пересечением  слева и  справа пусть  быть левым соседом  и разреши  быть правильным соседом  в Т        создать новый граничный луч  если , или создать  если п является правым высшим из q и s, иначе создать         заменять  с вновь созданным  в Т        удалить из Q любое пересечение между  и         удалить из Q любое пересечение между  и         вставить в Q любое пересечение между  и         вставить в Q любое пересечение между  и         записывать п как вершина  и  и база         вывести граничные сегменты  и     конецв конце концоввывести оставшиеся граничные лучи в Т

Взвешенные сайты и диски

Как описывает Fortune в исх. [1]модифицированная версия алгоритма развертки линии может быть использована для построения диаграммы Вороного с аддитивным взвешиванием, в которой расстояние до каждого сайта смещено на вес сайта; это можно эквивалентно рассматривать как диаграмму Вороного набора дисков, центрированных в узлах с радиусом, равным его весу.

Взвешенные сайты могут использоваться для контроля площадей ячеек Вороного при использовании диаграмм Вороного для построения карты деревьев. В аддитивно взвешенной диаграмме Вороного биссектриса между узлами, как правило, является гиперболой, в отличие от невзвешенных диаграмм Вороного и диаграммы мощности дисков, для которых это прямая.

Рекомендации

  1. ^ а б де Берг, Марк; ван Кревельд, Марк; Овермарс, Марк; Шварцкопф, Отфрид (2000), Вычислительная геометрия (2-е изд. Перераб.), Springer-Verlag, ISBN  3-540-65620-0 Раздел 7.2: Вычисление диаграммы Вороного: стр. 151–160.
  2. ^ Остин, Дэвид, Диаграммы Вороного и день на пляже, Столбец функций, Американское математическое общество.
  3. ^ Стивен Форчун. Алгоритм Sweepline для диаграмм Вороного. Материалы второго ежегодного симпозиума по вычислительной геометрии.. Yorktown Heights, Нью-Йорк, США, стр. 313–322. 1986 г. ISBN  0-89791-194-6. Цифровая библиотека ACMSpringerLink
  4. ^ Кенни Вонг, Хауси А. Мюллер, Эффективная реализация алгоритма развертки Фортуны для диаграмм Вороного, CiteSeerX  10.1.1.83.5571.

внешняя ссылка