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

[Amicus Plato]

Читаю сейчас про нейронные сети и вычитала очень любопытную вещь!
Такая простая и такая неожиданно интересная! К сетям имеет отношение опосредованное, а прямое — к геометрии.
Называется: многоугольники (диаграмма, разбиение) Вороного-Дирихле.
Смысл разбиения элементарен.
У нас есть плоскость, на которой мы должны поставить конечное множество точек (как минимум, две).
Эти точки зададут разбиение плоскости на области, в каждой из которых любая точка будет более близка к своей выделенной точке. Это лучше показать на картинке.
Для двух точек это, как нетрудно догадаться, выглядит так:

(Граница — серединный перпендикуляр отрезка, соединяющего эти точки).
Для трех точек получим:
1. 2.
Для четырех:
1. 2.
И так далее.
Таким образом, любое конечное множество точек на плоскости задаст разбиение на области, в каждой из которых будут находиться точки, лежащие ближе к данной точке, чем к какой бы то ни было другой.

Названа эта диаграмма в честь русского учёного Георгия Феодосьевича Вороного (1868—1908).
У него учился сам Вацлав Серпинский!
А вот как выглядит разбиение "в общем виде":

Картинка из Википедии.
Оттуда же ссылка на он-лайн построитель разбиения Вороного:
hirak99.googlepages.com/voronoi
А от меня совет: точки можно таскать мышкой по плоскости и смотреть, как изменяется разбиение!
Завораживающее зрелище!
А в правом верхнем углу панель навигации: можно вращать, изменять масштаб, и сдвигать во все стороны. Красота!

@темы: Поп-математика, Amicus Plato

Comments

[format_elitny]

Очень красивые картинки. А вы не знаете, на какие многоугольники разбивается плоскость при таком разбиении при большом числе случайных точек? В вероятностном смысле. На вид треугольников нет совсем, мало четырехугольников, больше 5-6-7-угольников. Может кто-то занимался такой задачей?

[Amicus Plato]

format_elitny
Хороший вопрос))
Надо подумать))
Я, честно говоря, впервые сегодня это увидела....
Очень интересно!

[format_elitny]

Единственное что точно видно и можно наверняка доказать (хотя я и не понимаю как), это то, что все такие многоугольники - выпуклые))

[Amicus Plato]

format_elitny
выпуклость доказать легко от противного.
Пусть есть невыпуклый многоугольник. Это лучше бы нарисовать... сейчас нарисую.

[Amicus Plato]

Возможны две разные ситуации:
Когда в невыпуклый многоугольник "врезается" один выпуклый, или когда несколько (именно в вогнутую часть):

Если с первым случаем легко доказать противоречие, то во втором надо чуть-чуть подумать.
Оно-то "видно", но как доказать строго?...

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

[format_elitny]

Да, точно! На самом деле не трудно.

[format_elitny]

Кстати. Все эти картинки с многоугольниками напоминают стереографические проекции многогранников.
И там и тут есть есть "замкнутые" и "разомкнутые" многоугольники.
Если на рисунках добавить к плоскости R^2 точку на бесконечности, и считать что все прямые, уходящие на бесконечнось, пересекаются в этой точке то получится еще более похоже.
Только есть отличие - в стереографической проекции отрезки заменены на дуги окружностей.

[Amicus Plato]

format_elitny
Я вообще второй день не могу понять, что же мне эти картинки напоминают!
Прямо дежа-вю какое-то!
Да, точно! Стереографические проекции!
А еще вот:

)))

[format_elitny]

Изображение не видно.

[Amicus Plato]

format_elitny
странно... мне видно...
Сейчас поищу другое.
Я имела в виду вот что-то типа таких "оптических иллюзий":
(только тут с цветами перебор вышел(( )

[Гость]

Диаграммы Вороного имеют непосредственное отношение к Support Vector Machines, используются в современной теории распознавания образов

[Amicus Plato]

Гость
Спасибо.
Не могли бы Вы рассказать поподробней?
Или ссылками поделиться?

[TWOTN]

Вообще диаграмма Вороного имеет прямую, тесную, и (!!!) взаимооднозначную связь с триангуляцией Делоне.
Штука весьма интересная.
А триангуляция имеет множество применений.

[Amicus Plato]

Парестезия
Я недавно вернулась с конференции. Там был доклад, не совсем из области моей деятельности, поэтому я поняла достаточно поверхностно, но всё равно очень интересно!
С помощью диаграмм Вороного делают оптимальную разбивку микросхем на непересекающиеся области для размещения на них модулей.

Вообще диаграмма Вороного имеет прямую, тесную, и (!!!) взаимооднозначную связь с триангуляцией Делоне.

Если бы вы написали об этом в сообществе (более или менее развернуто), было бы замечательно!