28 апреля исполнилось
145 лет со дня рождения выдающегося математика
Георгия Феодосьевича Вороного.
ВикипедияГеоргий Феодосьевич Вороной (16 (28) апреля 1868 — 7 (20) ноября 1908) — известный российский математик украинского происхождения. Член-корреспондент Петербургской академии наук с 01.12.1907.
БиографияГеоргий Феодосьевич Вороной родился в деревне Журавка Полтавской губернии (ныне Черниговская область).
С 1889 года обучался в Санкт-Петербургском университете у Андрея Маркова.
В 1894 году защитил магистерскую диссертацию «О целых числах, зависящих от корня уравнения третьей степени». В том же году был избран профессором Варшавского университета, где изучал цепные дроби. У Вороного обучался Вацлав Серпинский.
В 1897 году защитил докторскую диссертацию «Об одном обобщении алгоритма непрерывных дробей», удостоенную премии имени Буняковского.
Диаграмма ВороногоДиаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
Названа в честь российского учёного Георгия Феодосьевича Вороного (1868—1908). Также известна как: мозаика Вороного, разбиение Вороного, разбиение Дирихле.
Об этом я очень давно писала в своем сообществе:
Диаграмма Вороного (читать)У нас есть плоскость, на которой мы должны поставить конечное множество точек (как минимум, две).
Эти точки зададут разбиение плоскости на области, в каждой из которых любая точка будет более близка к своей выделенной точке. Это лучше показать на картинке.
Для двух точек это, как нетрудно догадаться, выглядит так:
(Граница — серединный перпендикуляр отрезка, соединяющего эти точки).
Для трех точек получим:
1. 2.
Для четырех:
1. 2.
И так далее.
Таким образом, любое конечное множество точек на плоскости задаст разбиение на области, в каждой из которых будут находиться точки, лежащие ближе к данной точке, чем к какой бы то ни было другой.
Названа эта диаграмма в честь русского учёного Георгия Феодосьевича Вороного (1868—1908).
У него учился сам Вацлав Серпинский!
А вот как выглядит разбиение "в общем виде":
Картинка из Википедии.
А вот он-лайн построитель разбиения Вороного:
randomexperiment.com/experiments/pages/voronoi....
А от меня совет: точки можно таскать мышкой по плоскости и смотреть, как изменяется разбиение!
Завораживающее зрелище!
А в правом верхнем углу панель навигации: можно вращать, изменять масштаб, и сдвигать во все стороны. Красота!ОтсюдаНу и добавка (снова из Википедии).
Алгоритм Форчуна и немногое другое )Алгоритм Форчуна построения диаграммы Вороного.
Алгоритм основан на применении заметающей прямой. Заметающая прямая — это вспомогательный объект, представляющий собой вертикальную прямую линию. На каждом шаге алгоритма диаграмма Вороного построена для множества, состоящего из заметающей прямой и точек слева от неё. При этом граница между областью Вороного прямой и областями точек состоит из отрезков парабол (так как геометрическое место точек, равноудалённых от заданной точки и прямой — это парабола). Прямая движется слева направо. Каждый раз, когда она проходит через очередную точку, эта точка добавляется к уже построенному участку диаграммы. Добавление точки к диаграмме при использовании двоичного дерева поиска имеет сложность `O(log n)`, всего точек `n`, а сортировка точек по `x`-координате может быть выполнена за `O(n log n)`, поэтому вычислительная сложность алгоритма Форчуна равна `O(n log n)`.
История
Впервые применение подобных конструкций приписывают Декарту в 1644 году. Дирихле использовал двумерные и трехмерные диаграммы Вороного в своём труде о квадратичных формах в 1850.
Свойства
Имеет тесную связь и взаимооднозначное соответствие с триангуляцией Делоне. А именно, если соединить рёбрами точки, области Вороного которых граничат друг с другом, полученный граф будет являться триангуляцией Делоне.