Распечатать запись Распечатать запись

Каждый в своей области и Вороной для всех

Клара Грима

Георгий Феодосьевич Вороной (1868-1908)

Я изучала математику, да, за ее высшую красоту, знаете ли, которую каждый получает ни за что.

Ну, это все смешно до тех пор, пока учитель ваших детей не попросит вас пойти и рассказать детям трехлетнего возраста о том, чем вы занимаетесь.

Конечно, можно просто сказать, что вы учитель, как и ваш преподаватель, и что вы учите таким вещам как числа, треугольники, квадраты и круги. Но это не то, что я делаю, я занимаюсь гораздо более сложными вещами!

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

Что такое диаграммы Вороного?

Ну… это разбиение метрического пространства на области, в которых находятся объекты, таким образом, что каждому объекту соответствует область пространства, образованная точками, которые находятся ближе к этому объекту, чем к любому другому.

Иначе говоря, пространство разделяется на области, содержащие точки или объекты, такого вида, что каждая точка принадлежит области, образованной всем, что ближе к этой точке, чем к какой-либо другой точке.

Например, если у нас есть набор из 8 точек на евклидовой плоскости, диаграммой Вороного является следующее разбиение плоскости:

Возьмем точку, например, зеленую точку на рисунке, и определим, какая из исходных 8 точек наиболее близка к ней. Эта точка находится в той области, куда попадает наша точка.

Это свойство диаграммы Вороного имеет непосредственные приложения, такие как поиск “ресторана’’ быстрого питания известной сети ресторанов, наиболее близкого к вам, к примеру, если вы путешествуете по Парижу:

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

“Представьте себе’’, — говорю, — “что герои Lunnis (Лос Луннис — испанский детский познавательный сериал со смешными персонажами) находятся на детской площадке, по одному в разных местах. И вдруг кто-то находит конфету, которая расположена так, как на этом рисунке’’.

“Чья это конфета?’’

Как и ожидалось, все ответы следовали закону, — “того, кто находится ближе’’. Но были и сомнения между Lucho (желтый), Lublú (синий цвет) и Lubina (ведьма), которые находятся поблизости.

Это был мой день.

Диаграмма Вороного служит для разделения двора на такие области, чтобы о каждом было известно, что в данной области все точки ближе к нему, чем к любому из его друзей.

“Давайте построим диаграмму Вороного двора чтобы видеть, кому достанется конфета.’’

“Lucho!’’ — кричали они, рискуя остаться безголосыми. Тогда мы бросали конфеты в разные области, и дети радостно кричали имя.

Я не знаю, может, они ничего не запомнили в тот день, но казалось, что это было весело.

Теперь, кроме разрешения конфликтов во дворе школы или ориентирования в поисках гамбургера, что такое и для чего используются диаграммы Вороного?

Во-первых, позвольте мне сказать вам, что эта структура называется по имени Георгия Вороного, русского математика, но она также известна под названием полигонов Тиссена (в честь Альфреда Тиссена, американского метеоролога) или двумерных сот Дирихле (в честь математика Густава Лежена Дирихле). И, конечно, еще как-нибудь, поскольку эта структура логична и интуитивно появляется всякий раз, когда возникает вопрос о близости.

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

Без сомнения, с исторической точки зрения достойное упоминания применение диаграммы Вороного появилось в работах Джона Сноу, которого многие считают отцом современной эпидемиологии, исследовавшего холеру, поразившую Лондон в 1854 году.

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

Затем он изучил расположение источников питьевой воды в городе и определил области Вороного для каждого из них. Рассчитав расстояния между местом жительства каждого погибшего и ближайшей водокачкой, он сделал вывод, что район, наиболее сильно пострадавший от холеры, соответствует области Вороного, связанной с водокачкой на Брод-стрит (Broad street), так как здесь умерло 73 из 83 человек.

После удаления ручки этой водокачки вспышка холеры была погашена. Ну почему же говорят, что математика не пригодна ни для чего… Это так, только Сноу не называл свои области областями Вороного по разным причинам, среди которых та, что Вороной в то время еще не родился.

С тех пор и до сегодняшнего дня диаграммы Вороного в двух и трех измерениях использовались в самых разных областях. Давайте рассмотрим некоторые их применения.

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

На рисунке выше препятствия красные, а синие пунктирные линии ограничивают области Вороного (да, мы можем строить диаграммы Вороного для объектов, отличных от точки). Если робот идет по синей линии, не будет столкновений.

Та же самая стратегия может быть использована в дипломатии для лавирования между конкурирующими интересами так, чтобы не вызывать подозрений, но не очевидно, что для данного случая разработан точный алгоритм…

Идея, которая похожа на ту, что используется для робота, выдвинута в работе Голда (C. M. Gold) 2006 года, в которой предложено применять эту же структуру для географических информационных систем, используя, опять же, границы областей для исключения столкновений с географическими объектами.

Другое применение этой диаграммы, например, определение максимального свободного пространства.

Представьте себе, что точками обозначены города, и мы хотим найти место для нежелательного объекта, рядом с которым никто не хочет находиться, например, атомную электростанцию, склад органических отходов или ресторан популярной сети. Естественно, всегда есть возможность расположить его в соседней стране, но это нехорошо. Мы ограничим проблему, считая, что нежелательный объект необходимо расположить в выпуклой оболочке городов. Интуитивно выпуклая оболочка множества точек на плоскости имеет форму, которую приняла бы эластичная резинка, если позволить ей окружить точки, которые можно считать гвоздиками. На рисунке внизу граница выпуклой оболочки зеленая.

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

В этом случае, чтобы расположить неприятный объект внутри области с зеленой границей, мы должны сделать так, чтобы ближайший к нему город был как можно дальше от него, то есть минимальное расстояние до него должно быть максимальным. Это достигается за счет размещения объекта в центре самого большого незаселенного пустого круга, который мы рисуем в области с зеленой границей. Ну вот! Центр этого круга будет в одной из вершин диаграммы Вороного.

Интересно, не правда ли? Однако это еще не все.

Пойдем в лес, потому что здесь также используются диаграммы Вороного в качестве исследовательского инструмента для анализа и предсказания влияния места, занимаемого деревьями, на эволюцию леса. Мой коллега и друг Мануэль Абейанас (Manuel Abellanas) из Политехнического университета Мадрида совместно с другими исследователями разработал Vorest, тот инструмент, о котором говорилось.

Это макроскопический уровень, но и на уровне микроскопическом мы можем найти работу, в которой применяются диаграммы Вороного. С 1974 года Ф.М. Ричардс (F.M. Richards), специалист по структурной биологии из Йельского университета и новатор в области изучения связи между белковыми структурами и их биологическими функциями, заявил об эффективности и актуальности такой трехмерной диаграммы для описания структуры протеинов.

Среди многочисленных работ, которые можно найти на эту тему, у нас есть, например, инструмент VORO3D, который позволяет создать 3D визуализацию структуры белка. Для этого, грубо говоря, рассматривается упаковка аминокислот, так что каждый кислотный остаток представляется точкой пространства. Поскольку аминокислота вблизи поверхности белка может дать открытую область Вороного, считается, что молекула ограничена частями сфер, так чтобы объем полученного тела не слишком отличался от действительного среднего объема молекулы.

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

Что еще?

Кости? Да, господа. Вообще говоря, в наших костях можно выделить две различные области: компактное и губчатое вещество.

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

Но кроме полезности этих структур, нельзя отрицать красоту и гармонию геометрии. Красота, кажется, не осталась незамеченной архитекторами и дизайнерами:

Город внутри небоскребов Вороного?

Но эта концепция настолько естественна и интуитивно понятна, что окрестности нескольких основных точек, выделенных по какой-то причине, можно найти в природе, верно?

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

Некоторые шерстинки толще, чем остальные?

Некоторые точки имеют иную влажность?

Некоторые точки на поверхности Солнца горячее?

Или это последний кусок льда?

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

Источник: http://amazings.es/2011/12/23/cada-uno-en-su-region-y-voronoi-en-la-de-todos/

Фотография Вороного взята отсюда: http://botinok.co.il/node/42783

Оставьте свой отзыв

Добавить изображение