XXIII городская научно-практическая конференция учащихся

«Юные исследователи – будущее Братска»

под эгидой Российской научно-социальной программы для

молодежи «Шаг в будущее»

На Вороном к соседу

Автор: Бабенко Ольга, учащаяся 7 класса МБОУ «Лицей №1» г. Братска Иркутской области 

Руководитель: Кокурина Любовь Михайловна, учитель математики первой квалификационной категории МБОУ «Лицей №1» г. Братска Иркутской области

г. Братск, Иркутская область

2019 год

СОДЕРЖАНИЕ

ВВЕДЕНИЕ        3

ГЛАВА 1. Диаграмма Вороного        4

1.1 Историческая справка        4

1.2 Построение и свойства диаграммы Вороного        4

ГЛАВА 2. Практическое применение диаграммы Вороного        6

2.1 Поиск ближайшего соседа        6

2.2 Поиск ближайшего эвакуационного выхода        6

2.3 Поиск пути в среде со статическими препятствиями        7

2.4 Ориентирование на местности        7

2.5 Оптимальная расстановка охранников        7

ЗАКЛЮЧЕНИЕ        8

СПИСОК ЛИТЕРАТУРЫ        9

Приложение А. Результаты поиска диаграммы в браузере Яндекс        I

Приложение Б. Построение и свойства диаграммы Вороного        II

Приложение В. Практическое применение диаграммы Вороного        IV

ВВЕДЕНИЕ

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

Так, я заинтересовалась тем, как решаются задачи геометрической близости на плоскости. Ключом к решению таких задач оказался планарный граф [1] называемый диаграммой Вороно́го.

Предмет изучения – диаграмма Вороно́го.

Объектная область исследования – геометрия, информатика, география.

Цель исследования – изучить свойства диаграммы Вороно́го и сферы её практического применения.

Задачи исследования:

• дать определение диаграммы Вороного;
• сформулировать свойства диаграммы Вороного;
• рассмотреть примеры практического применения диаграммы Вороного.

Гипотеза: диаграмма Вороного является эффективным инструментом для решения задач на геометрическую близость.

Методы исследования:

- изучение литературы по данной проблематике;

- анализ и систематизация собранных данных;

- практическое применение диаграммы Вороного.

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

ГЛАВА 1. Диаграмма Вороного

1.1 Историческая справка

Диаграмма Вороно́го названа в честь своего создателя - русского ученого Георгия Феодосьевича Вороно́го (1868-1908 гг.). Однако первое использование этой диаграммы встречается в труде Рене Декарта (1596-1650 гг.) «Начала философии» (1644 г.). Декарт предложил таким образом делить Вселенную на зоны гравитационного влияния звезд [2].

В наше время работы Вороного используют специалисты разных областей знаний практически во всех странах мира. За рубежом его работы известны даже больше, чем на постсоветском пространстве. В англоязычных странах диаграмма Вороного известна под названием voronoi diagram, если ввести это название в строку поиска интернет браузера найдется 19 млн. результатов (см. Приложение А, рис. А.1), если ввести в поисковик название диаграммы на русском языке, результатов поиска будет только 1 млн. (см. Приложение А, рис. А.2).

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

Диаграмму Вороного также называют полигонами Вороного, ячейками Вороного или мозаикой Вороного. Кроме научного применения диаграмма Вороного встречается в природе, ею вдохновляются художники, архитекторы и конструкторы (см. Приложение А, рис. А.3) [4, 5].

1.2 Построение и свойства диаграммы Вороного

Диаграмма Вороного - это разбиение плоскости с n-ым количеством точек (узлов) на множество выпуклых многогранников (полигонов) таким образом, что каждый из них содержит один узел и любая точка внутри данного полигона ближе к своему узлу, чем к любому другому (см. Приложение Б, рис. Б.1) .

Построение диаграммы Вороного:

Полигоны образуются пересечением срединных перпендикуляров к отрезкам, соединяющим узлы (см. Приложение Б, рис. Б.2).

Свойства диаграммы Вороного [3]:

• Каждая из n исходных точек множества принадлежит в точности одному полигону Вороного. Поэтому, если некая точка находится внутри полигона, то узел этого полигона является ближайшим соседом этой точки среди множества других узлов (см. Приложение Б, рис. Б.2).
• Точка пересечения рёбер диаграммы называется вершиной (см. Приложение Б, рис. Б.1).
• Поскольку диаграмма Вороного содержит вершины и рёбра она является графом. Что вытекает из определения графа:

Граф - абстрактный математический объект, представляющий собой множество вершин и набор рёбер - соединений между вершинами.

• Поскольку диаграмма Вороного представлена отрезками и геометрическими фигурами, она является диаграммой. Что вытекает из определения диаграммы:

Диагра́мма - графическое представление данных линейными отрезками или геометрическими фигурами.

• Каждая вершина диаграммы Вороного является центром окружности, проведённой через ближайшие к ней узлы (см. Приложение Б, рис. Б.3). Вершина диаграммы равноудалена от этих узлов.
• Ближайшую пару узлов определяет ребро диаграммы Вороного. Любая точка, находящаяся на ребре диаграммы Вороного равноудалена от ближайших к ребру узлов (см. Приложение Б, рис. Б.4).
• Вершиной диаграммы Вороного для узлов, являющихся вершинами правильного многоугольника, будет центр описанной окружности данного многоугольника (см. Приложение Б, рис. Б.5).

ГЛАВА 2. Практическое применение диаграммы Вороного

2.1 Поиск ближайшего соседа

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

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

В какой-то местности есть n-ое количество почтовых отделений. И человек, находясь в определённом месте, спрашивает о ближайшем почтовом отделении. Проблема решается путём построения диаграммы Вороного для всех почтовых отделений. Местоположение человека будет отнесено к одной из областей, и ближайшим будет почтовое отделение, которое в ней находится [6] (см. Приложение В, рис. В.1).

Современным примером такой задачи будет, например, поиск ближайшего супермаркета или отделения банка. Я применила диаграмму Вороного к аптекам и банкоматам, расположенным в жилом районе Энергетик города Братска (см. рис. В.2, В.3).

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

Например: жителям 1-го и 4-го микрорайонов приходится дальше всех добираться до ближайших к ним аптек (Приложение В, рис. В.2). К ближайшему банкомату также дальше всех добираться жителям 1-го микрорайона (Приложение В, рис. В.3).

2.2 Поиск ближайшего эвакуационного выхода

25 марта 2018 г. в Кемерово случился крупный пожар в торгово-развлекательном центре «Зимняя вишня», унёсший 64 жизни. Одной из причин большого количества жертв явилось то, что люди не успели вовремя эвакуироваться через пожарные выходы.

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

Для повышения эффективности противопожарной системы можно использовать диаграмму Вороного. Её применение позволяет определить для каждого эвакуационного выхода граничную область. Для людей в этой области данный выход будет ближайшим (Приложение В, рис. В.4). Чтобы организовать эвакуацию людей через ближайший к ним выход в неосвещенном и задымленном помещении можно использовать светящиеся в темноте фотолюминесцентные знаки, расположенные по стенам и на полу на путях эвакуации.

2.3 Поиск пути в среде со статическими препятствиями

Решение задачи построения маршрута с учётом препятствий сводится к построению диаграммы Вороного, узлами которой будут являться огибаемые препятствия (Приложение В, рис. В.5). Диаграмма Вороного может применяться для навигации мобильных роботов. Например, робот-пылесос, огибая препятствия в комнате, движется по границам ячеек диаграммы Вороного.

2.4 Ориентирование на местности

Представим такую ситуацию, вы отправились кататься на моторной лодке по Братскому водохранилищу, и у вас закончилось горючее. При этом вы знаете свое точное место нахождения. Как определить, до какого населенного пункта грести вёслами ближе и быстрее? Если у вас при себе есть карта, диаграмма Вороного даст ответ на вопрос, к какому населенному пункту вы находитесь ближе всего (Приложение В, рис. В.6).

2.5 Оптимальная расстановка охранников

Диаграмму Вороного можно применять для оптимальной расстановки охранников или камер наблюдения на охраняемых объектах. На рис. В.7 показана расстановка охранников в галерее. За узлы диаграммы приняты экспонаты.

Оптимальным будет такая расстановка охранников, при которой каждый из них со своего наблюдательного пункта может визуально осматривать как можно большее число экспонатов, при этом не должно быть «слепых» зон, не просматриваемых охранниками. Каждый охранник может поворачиваться на 360°.

ЗАКЛЮЧЕНИЕ

Вернёмся к вопросу, с которого я начала свое исследование – к зонам ответственности волейболистов на игровом поле. Примеры применения диаграммы Вороного, которые я привела выше, относились к статическим объектам. Волейбол же игра динамичная, игроки постоянно меняют свое положение на поле, если каждый игрок – узел диаграммы, то полигоны Вороного во время игры будут постоянно меняться (см Приложение В, рис. В.8).

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

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Диаграмма Вороного в 2D // Персональный сайт Максима Иванова MAXimal.ru [Электронный ресурс]. URL: http://www.e-maxx-ru.1gb.ru/algo/voronoi_diagram_2d_n4 (дата обращения: 17.11.18).

2. Клара Грима. Каждый в своей области и Вороной для всех // Персональный сайт Калининой Е. А. «Математика, которая мне нравится» [Электронный ресурс]. URL: http://hijos.ru/2011/12/28/kazhdyj-v-svoej-oblasti-i-voronoj-dlya-vsex/ (дата обращения: 17.11.18).

3. Геометрическое моделирование и компьютерная графика: вычислительные и алгоритмические основы. Курс лекций / Д.М.Васильков. – Минск: БГУ, 2011 [Электронный ресурс]. URL: http://www.elib.bsu.by (дата обращения: 20.11.18).

4. QuantZero. Диаграмма Вороного и её применения // [Электронный ресурс]. URL: https://habr.com/post/309252/ (дата обращения: 20.11.18).

5. Диаграмма Вороного // Дизайн-завод «Flacon» [Электронный ресурс]. URL: http://makefabricationstudio.ru/diagramma-voronogo/ (дата обращения: 20.11.18).

6. Шишкалова Н.Г. Яркая звезда Георгия Вороного // Страна знаний. Научно-популярный журнал для юношества [Электронный ресурс]. URL:  https://www.krainaz.org/2018-02/359-voronoy (дата обращения: 23.11.18).