Диаграмма Вороного

Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.

Названа в честь российского учёного Георгия Феодосьевича Вороного. Также известна как: мозаика Вороного, разбиение Вороного, разбиение Дирихле.

История

Впервые применение подобных конструкций приписывают Декарту в 1644 году. Дирихле использовал двумерные и трехмерные диаграммы Вороного в своём труде о квадратичных формах в 1850.

Свойства

Имеет тесную связь и взаимооднозначное соответствие с триангуляцией Делоне. А именно, если соединить рёбрами точки, области Вороного которых граничат друг с другом, полученный граф будет являться триангуляцией Делоне.

Алгоритмы построения

Простой алгоритм

Рассмотрим серединный перпендикуляр отрезка, соединяющего некоторую пару точек <math>p</math> и <math>q</math>. Этот перпендикуляр разбивает плоскость на две полуплоскости <math>H_{pq}</math> и <math>H_{qp}</math>, причём область Вороного точки p целиком содержится в одной из них, а область точки <math>q</math> — в другой. Область Вороного <math>V_p</math> точки <math>p</math> совпадает с пересечением всех таких полуплоскостей <math>H_{pq}</math>:

<math>V_p = \cap_{q \in S / \{p\}} H_{pq}</math>.

Таким образом, решение задачи сводится к вычислению такого пересечения для каждой точки <math>p</math>. Алгоритм может быть реализован с вычислительной сложностью <math>O(n^2\log n)</math>.

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

Алгоритм основан на применении заметающей прямой. Заметающая прямая — это вспомогательный объект, представляющий собой вертикальную прямую линию. На каждом шаге алгоритма диаграмма Вороного построена для множества, состоящего из заметающей прямой и точек слева от неё. При этом граница между областью Вороного, прямой и областями точек состоит из отрезков парабол (так как геометрическое место точек, равноудалённых от заданной точки и прямой — это парабола). Прямая движется слева направо. Каждый раз, когда она проходит через очередную точку, эта точка добавляется к уже построенному участку диаграммы. Добавление точки к диаграмме при использовании двоичного дерева поиска имеет сложность <math>O(\log n)</math>, всего точек <math>n</math>, а сортировка точек по <math>x</math>-координате может быть выполнена за <math>O(n \log n)</math>, поэтому вычислительная сложность алгоритма Форчуна равна <math>O(n \log n)</math>.

Рекурсивный алгоритм

Основная идея рекурсивного алгоритма заключается в использовании метода динамического программирования. Исходное множество точек <math>S</math> разбивается на два подмножества <math>S_1</math> и <math>S_2</math>, для каждого из них строится диаграмма Вороного, а затем полученные диаграммы объединяются в одну. Разбиение множества <math>S</math> осуществляется при помощи прямой, разделяющей плоскость на две полуплоскости, так, чтобы в обеих полуплоскостях находилось примерно одинаковое количество точек. Объединение диаграмм Вороного множеств <math>S_1</math> и <math>S_2</math> может быть выполнено за время <math>O(n)</math>, поэтому вычислительная сложность алгоритма равна <math>O(n \log n)</math>.

Обобщения

Диаграмму Вороного очевидным образом можно определить для множества точек в произвольном евклидовом пространстве, необязательно двумерном. Имеет место следующее утверждение: в <math>k</math>-мерном пространстве количество симплексов <math>k</math>-мерной триангуляции Делоне множества из <math>n</math> точек может достигать <math>O(n^{\lceil \frac k 2 \rceil})</math>. Следовательно, такой же порядок имеют расходы памяти, требуемой для хранения двойственной диаграммы Вороного.

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

Множество S может состоять не только из точек, но и из любых объектов, для которых определено расстояние до произвольной точки плоскости. В этом случае элементы множества S называют сайтами. В качестве примера можно привести диаграмму Вороного многоугольника, где сайты — это вершины и рёбра многоугольника. Такие диаграммы используются для построения срединных осей и широко применяются в задачах анализа изображений. Граница областей диаграммы Вороного многоугольника представляет собой объединение отрезков прямых и парабол.

Применение

Разбиение Вороного применяется в вычислительном материаловедении для создания синтетических поликристаллических агрегатов. Также используется в компьютерной графике для случайного разбиения поверхностей.

Метод Гольда (или «метод похищения площади») — метод интерполяции функции в 2D, применяемый, например, в геодезии. Строится диаграмма Вороного всех точек, после этого к ней добавляется искомая точка. Новая ячейка «отбирает» площадь у имеющихся; чем больше площади позаимствовано у (x_i, y_i, z_i), тем больше коэффициент при этой точке.

Также разбиение Вороного применяется при нахождении верхней оценки хроматического числа для евклидова пространства (проблема Нелсона-Эрдёша-Хадвигера) размерности 2 или 3. Здесь рассматривают разбиение плоскости на многоугольники Вороного для заданной решётки. Наилучшая оценка была найдена, как для 2-мерного, так и для 3-мерного пространств, при рассмотрении симметричного разбиения. Например, замощение плоскости шестиугольниками (в данном случае шестиугольник — многоугольник Вороного).

См. также

• Задача поиска ближайшего соседа
• Ячейка Вигнера — Зейтца

Ссылки

• [www.ams.org/featurecolumn/archive/voronoi.html Алгоритм Форчуна] (англ.)
• [rain.ifmo.ru/cat/view.php/vis/geometry/voronoi-diagram-2011 Визуализатор алгоритма Форчуна]

Отрывок, характеризующий Диаграмма Вороного

– Вот еще одного ведут! – сказал один из офицеров, указывая на французского пленного драгуна, которого вели пешком два казака.
Один из них вел в поводу взятую у пленного рослую и красивую французскую лошадь.
– Продай лошадь! – крикнул Денисов казаку.
– Изволь, ваше благородие…
Офицеры встали и окружили казаков и пленного француза. Французский драгун был молодой малый, альзасец, говоривший по французски с немецким акцентом. Он задыхался от волнения, лицо его было красно, и, услыхав французский язык, он быстро заговорил с офицерами, обращаясь то к тому, то к другому. Он говорил, что его бы не взяли; что он не виноват в том, что его взяли, а виноват le caporal, который послал его захватить попоны, что он ему говорил, что уже русские там. И ко всякому слову он прибавлял: mais qu'on ne fasse pas de mal a mon petit cheval [Но не обижайте мою лошадку,] и ласкал свою лошадь. Видно было, что он не понимал хорошенько, где он находится. Он то извинялся, что его взяли, то, предполагая перед собою свое начальство, выказывал свою солдатскую исправность и заботливость о службе. Он донес с собой в наш арьергард во всей свежести атмосферу французского войска, которое так чуждо было для нас.
Казаки отдали лошадь за два червонца, и Ростов, теперь, получив деньги, самый богатый из офицеров, купил ее.
– Mais qu'on ne fasse pas de mal a mon petit cheval, – добродушно сказал альзасец Ростову, когда лошадь передана была гусару.
Ростов, улыбаясь, успокоил драгуна и дал ему денег.
– Алё! Алё! – сказал казак, трогая за руку пленного, чтобы он шел дальше.
– Государь! Государь! – вдруг послышалось между гусарами.
Всё побежало, заторопилось, и Ростов увидал сзади по дороге несколько подъезжающих всадников с белыми султанами на шляпах. В одну минуту все были на местах и ждали. Ростов не помнил и не чувствовал, как он добежал до своего места и сел на лошадь. Мгновенно прошло его сожаление о неучастии в деле, его будничное расположение духа в кругу приглядевшихся лиц, мгновенно исчезла всякая мысль о себе: он весь поглощен был чувством счастия, происходящего от близости государя. Он чувствовал себя одною этою близостью вознагражденным за потерю нынешнего дня. Он был счастлив, как любовник, дождавшийся ожидаемого свидания. Не смея оглядываться во фронте и не оглядываясь, он чувствовал восторженным чутьем его приближение. И он чувствовал это не по одному звуку копыт лошадей приближавшейся кавалькады, но он чувствовал это потому, что, по мере приближения, всё светлее, радостнее и значительнее и праздничнее делалось вокруг него. Всё ближе и ближе подвигалось это солнце для Ростова, распространяя вокруг себя лучи кроткого и величественного света, и вот он уже чувствует себя захваченным этими лучами, он слышит его голос – этот ласковый, спокойный, величественный и вместе с тем столь простой голос. Как и должно было быть по чувству Ростова, наступила мертвая тишина, и в этой тишине раздались звуки голоса государя.
– Les huzards de Pavlograd? [Павлоградские гусары?] – вопросительно сказал он.
– La reserve, sire! [Резерв, ваше величество!] – отвечал чей то другой голос, столь человеческий после того нечеловеческого голоса, который сказал: Les huzards de Pavlograd?
Государь поровнялся с Ростовым и остановился. Лицо Александра было еще прекраснее, чем на смотру три дня тому назад. Оно сияло такою веселостью и молодостью, такою невинною молодостью, что напоминало ребяческую четырнадцатилетнюю резвость, и вместе с тем это было всё таки лицо величественного императора. Случайно оглядывая эскадрон, глаза государя встретились с глазами Ростова и не более как на две секунды остановились на них. Понял ли государь, что делалось в душе Ростова (Ростову казалось, что он всё понял), но он посмотрел секунды две своими голубыми глазами в лицо Ростова. (Мягко и кротко лился из них свет.) Потом вдруг он приподнял брови, резким движением ударил левой ногой лошадь и галопом поехал вперед.
Молодой император не мог воздержаться от желания присутствовать при сражении и, несмотря на все представления придворных, в 12 часов, отделившись от 3 й колонны, при которой он следовал, поскакал к авангарду. Еще не доезжая до гусар, несколько адъютантов встретили его с известием о счастливом исходе дела.
Сражение, состоявшее только в том, что захвачен эскадрон французов, было представлено как блестящая победа над французами, и потому государь и вся армия, особенно после того, как не разошелся еще пороховой дым на поле сражения, верили, что французы побеждены и отступают против своей воли. Несколько минут после того, как проехал государь, дивизион павлоградцев потребовали вперед. В самом Вишау, маленьком немецком городке, Ростов еще раз увидал государя. На площади города, на которой была до приезда государя довольно сильная перестрелка, лежало несколько человек убитых и раненых, которых не успели подобрать. Государь, окруженный свитою военных и невоенных, был на рыжей, уже другой, чем на смотру, энглизированной кобыле и, склонившись на бок, грациозным жестом держа золотой лорнет у глаза, смотрел в него на лежащего ничком, без кивера, с окровавленною головою солдата. Солдат раненый был так нечист, груб и гадок, что Ростова оскорбила близость его к государю. Ростов видел, как содрогнулись, как бы от пробежавшего мороза, сутуловатые плечи государя, как левая нога его судорожно стала бить шпорой бок лошади, и как приученная лошадь равнодушно оглядывалась и не трогалась с места. Слезший с лошади адъютант взял под руки солдата и стал класть на появившиеся носилки. Солдат застонал.
– Тише, тише, разве нельзя тише? – видимо, более страдая, чем умирающий солдат, проговорил государь и отъехал прочь.
Ростов видел слезы, наполнившие глаза государя, и слышал, как он, отъезжая, по французски сказал Чарторижскому:
– Какая ужасная вещь война, какая ужасная вещь! Quelle terrible chose que la guerre!
Войска авангарда расположились впереди Вишау, в виду цепи неприятельской, уступавшей нам место при малейшей перестрелке в продолжение всего дня. Авангарду объявлена была благодарность государя, обещаны награды, и людям роздана двойная порция водки. Еще веселее, чем в прошлую ночь, трещали бивачные костры и раздавались солдатские песни.