[Amicus Plato]

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.
Свойства
Имеет тесную связь и взаимооднозначное соответствие с триангуляцией Делоне. А именно, если соединить рёбрами точки, области Вороного которых граничат друг с другом, полученный граф будет являться триангуляцией Делоне.

@темы: История математики, Люди

Comments

[All_ex]

Amicus Plato, И снова спасибо!... ... построитель действительно прикольный...

[Amicus Plato]

All_ex,

построитель действительно прикольный...

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

[All_ex]

Имеет тесную связь и взаимооднозначное соответствие с триангуляцией Делоне - У меня один коллега интересуется этой триангуляцией... Вот надо будет подсказать...

[~ghost]

Amicus Plato, Спасибо!)
что-то "ужасно красивое".. ))

[Amicus Plato]

~ghost,

что-то "ужасно красивое".. ))

Ага! ))