Алгоритм Форчуна

Алгоритм Форчуна — это алгоритм заметающей прямой для генерации диаграммы Вороного из набора точек на плоскости за время O${\displaystyle (n\log n)}$ с использованием памяти O(n)^[1][2]. Алгоритм первоначально опубликовал Стивен Форчун в 1986 в своей статье «Алгоритм заметающей прямой для диаграмм Вороного»^[3].

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

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

Так как имеется O(n) событий для обработки (каждое ассоциировано с некоторым свойством диаграммы Вороного) и времени O(log n) для обработки события (которое состоит из постоянного числа поисков по двоичному дереву и операций очереди с приоритетом), общее время равно ${\displaystyle O(n\log n)}$.

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

Пусть ${\displaystyle *(z)}$ будет преобразованием ${\displaystyle *(z)=(z_{x},z_{y}+d(z))}$,
  где ${\displaystyle d(z)}$ — евклидово расстояние между  z и ближайшей точкой
Пусть T будет «береговой линией»
Пусть ${\displaystyle R_{p}}$ будет областью, покрывающей точку p.
Пусть ${\displaystyle C_{pq}}$ будет граничным лучом между точками p и q.
Пусть ${\displaystyle p_{1},p_{2},...,p_{m}}$ будут точками с минимальной y-координатой, упорядоченными по x-координате
${\displaystyle Q\gets S-{p_{1},p_{2},...,p_{m}}}$
создаёт начальные вертикальные граничные лучи ${\displaystyle C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},...C_{p_{m-1},p_{m}}^{0}}$
${\displaystyle T\gets *(R_{p_{1}}),C_{p_{1},p_{2}}^{0},*(R_{p_{2}}),C_{p_{2},p_{3}}^{0},...,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*(R_{p_{m}})}$
пока не IsEmpty(Q) выполнить
    ${\displaystyle p\gets \mathrm {DeleteMin} (Q)}$
    в случае если 
    p является точкой в ${\displaystyle *(V)}$:
        Находим область ${\displaystyle *(R_{q})}$ в T, содержащую p,
          ограниченную кривой ${\displaystyle C_{rq}}$ слева и кривой ${\displaystyle C_{qs}}$ справа
        создаём новые граничные лучи ${\displaystyle C_{pq}^{-}}$ и ${\displaystyle C_{pq}^{+}}$ с основанием p
        заменяем ${\displaystyle *(R_{q})}$ на ${\displaystyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$ в T
        удаляем из Q любое пересечение между ${\displaystyle C_{rq}}$ и ${\displaystyle C_{qs}}$
        вставляем в Q любое пересечение ${\displaystyle C_{rq}}$ и ${\displaystyle C_{pq}^{-}}$
        вставляем в Q любое пересечение ${\displaystyle C_{pq}^{+}}$ и ${\displaystyle C_{qs}}$
    p является вершиной Вороного в ${\displaystyle *(V)}$:
        пусть p будет пересечением ${\displaystyle C_{qr}}$ слева и ${\displaystyle C_{rs}}$ справа
        пусть ${\displaystyle C_{uq}}$ будет левым соседом ${\displaystyle C_{qr}}$ и
          пусть ${\displaystyle C_{sv}}$ будет правым соседом ${\displaystyle C_{rs}}$ в T
        создаём новый граничный луч ${\displaystyle C_{qs}^{0}}$, если ${\displaystyle q_{y}=s_{y}}$,
          или создаём ${\displaystyle C_{qs}^{+}}$, если p правая часть более высокой  из q и s,
          в противном случае создаём ${\displaystyle C_{qs}^{-}}$
        заменяем ${\displaystyle C_{qr},*(R_{r}),C_{rs}}$ на вновь созданную ${\displaystyle C_{qs}}$ в T
        удаляем из Q любое пересечение ${\displaystyle C_{uq}}$ и ${\displaystyle C_{qr}}$
        удаляем из Q любое пересечение ${\displaystyle C_{rs}}$ и ${\displaystyle C_{sv}}$
        вставляем в Q любое пересечение ${\displaystyle C_{uq}}$ и ${\displaystyle C_{qs}}$
        вставляем в Q любое пересечение ${\displaystyle C_{qs}}$ и ${\displaystyle C_{sv}}$
        записываем p как вершину ${\displaystyle C_{qr}}$ и ${\displaystyle C_{rs}}$ и основание ${\displaystyle C_{qs}}$
        выводим сегменты границ ${\displaystyle C_{qr}}$ и ${\displaystyle C_{rs}}$
    конец в случае
конец пока
выводим оставшиеся граничные лучи из T

Как указывает Форчун^[5], модифицированная версия алгоритма заметающей прямой может быть использована для построения аддитивно взвешенной диаграммы Вороного, в которой расстояние до каждой точки нейтрализуется весом точки. Это можно рассматривать эквивалентно как диаграмма Вороного набора дисков с центрами в точках и радиусом, равным весу точки.

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

• Реализация Стивена Форчуна на C
• Алгоритм Форчуна для диаграмм Вороного, реализованный на C++
• Алгоритм Форчуна, реализованный на JavaScript