Данная работа посвящена изучению задачи об охране картинной галереи в случае, когда план галереи представляет собой выпуклый многогранник. Проводится обзор известных ранее результатов. Приведены результаты, которые стали основой для разработки алгоритма расстановки охранников, а также приведено описание применяемого алгоритма.
Идентификаторы и классификаторы
Известно достаточно много модификаций данной задачи, одной из которых посвящена эта работа. В данной работе осуществляется переход к трехмерному аналогу исходной задачи, т. е. план картинной галереи представлен в виде выпуклого многогранника, а охранник (средство наблюдения), расположенный в его вершине – точкой, а также приводится доказательство теоремы, которая дает оценку минимального числа охранников для наблюдения за поверхностью. Область видимости охранника ограничена поверхностью трехмерного объекта наблюдения. Необходимо оценить, какое наименьшее количество охранников (средств наблюдения) иногда необходимо и всегда достаточно для того, чтобы вся поверхность многогранника находилась под присмотром. Единственная нетривиальная теорема об охране картинной галереи, известная для трехмерного случая, касается случая внешней видимости для охранников, ограниченных поверхностью выпуклого многогранника. Эквивалентная задача в размерности 2 тривиальна: n 2 охранников всегда необходимо и достаточно для защиты внешней части выпуклого многоугольника.
Список литературы
1. O’Rourke J. Art Gallery Theorems and Algorithms. - UK: Oxford University Press, 1987.
2. Nishizeki T. Lower bounds on the cardinality of the maximum matchings of planar graphs // Carnegie-Mellon tech. report. - 1977.
3. Nishizeki T., Baybars I. Lower bounds on the cardinality of the maximum matchings of planar graphs // Carnegie-Mellon tech. report. - 1977.
4. O’Rourke J. Art Gallery Theorems and Algorithms. - UK: Oxford University Press, 1987.
5. Balinski M.L. On the graph structure of convex polyhedral in n-space // Paci c Journal of Mathematics. - 1961.
6. Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах // MAXimal.
Выпуск
Другие статьи выпуска
В статье рассматриваются метод обеспечения конфиденциальности данных средствами Цифровой Стеганографии, использующий в качестве файлов-контейнеров изображения формата GIF, описывается и производится возможная атака на данный метод. Как результат, предлагаются возможные средства повышения стойкости системы против проводимой атаки.
В работе проводится обсуждение полного решения одной задачи преобразования плоскости, относящейся как к математическому анализу, так и к аналитической геометрии. Приведено подробное решение задачи, базирующегося на достаточно простых топологических понятиях, при этом демонстрирующее досконально чёткое исследование вопроса.
Построение оптимальной логистической сети имеет несомненный интерес как с точки зрения минимизации транспортных расходов, так и относительно времени доставки грузов. Данная работа посвящена построению программного комплекса для получения оптимального транспортного пути между заданными точками (магазин - склад). Основой данного комплекса является сеть Штейнера, что придает исследованию строгое математическое обоснование.
При ограничениях определенного вида в исходной экстремальной задаче методы внутренних и внешних штрафных функций логично комбинировать. Это комбинирование обуславливается достаточно конкретным видом ограничений, но, как оказывается, сохраняет теоретическую сходимость при тех же условиях, что и для “чистых” методов.
Работа посвящена построению преобразования Бьянки для поверхностей вращения постоянной отрицательной гауссовой кривизны. Поверхностями вращения постоянной отрицательной гауссовой кривизны являются волчок Минга, спираль Минга, псевдосфера (поверхность Бельтрами). Построенное преобразование Бьянки для Minding coil. Исследуемые поверхности описываются с использованием эллиптических интегралов. С помощью математического пакета построены Minding coil и его преобразование Бьянки. Исследуемые поверхности описываются с использованием эллиптических интегралов.
Итоговым результатом статьи является теоретико-игровая модель поиска компромиссного решения Центрального и коммерческого банков при организации кредитной политики. Исследования производятся методами математического и компьютерного моделирования в рамках теории иерархических игр.
В статье предлагается строгий вариант известного конструктивного доказательства теоремы существования меры длины отрезка путем последовательной укладки эталона и его двоичных частей.
Предлагается новый, по сути нечисловой, подход к изучению структуры кластерного разбиения с возможностью сравнения нескольких кластеризаций одного и того же конечного множества объектов. Подход основан на представлении кластеризуемых объектов и формирующих признаков этих объектов точками одного и того же искусственно построенного универсального пространства. При этом предложены как количественные характеристики рассматриваемых кластеризаций, так и способ чисто визуального анализа даже в случае, когда количество формирующих разбиения показателей достаточно велико, поскольку размерность универсального пространства может выбираться практически произвольно.
В работе построены сферические изображения кубических поверхностей вращения. Написана программа на языке MatLab, которая визуализирует процесс построения сферического образа.
В работе исследуются полусимметрические связности трехмерных групп Ли с левоинвариантными (псевдо)римановыми метриками и симметрическим тензором Риччи. Получена полная классификация таких полусимметрических связностей на трехмерных метрических группах Ли.
Рассматриваются методы математического и компьютерного моделирования трудовых процессов промышленных предприятий, персонал которых способен сократить потери ресурсов и простои оборудования. Для реального предприятия промышленности разработана компьютерная модель обоснования оптимальных параметров механизма стимулирования, описаны вычислительные эксперименты и рассмотрены условия его внедрения на практике.
Работа посвящена изучению преобразования Бианки для псевдосферы.
Издательство
- Издательство
- АлтГУ
- Регион
- Россия, Барнаул
- Почтовый адрес
- 656049, Алтайский край, город Барнаул, проспект Ленина, дом 61
- Юр. адрес
- 656049, Алтайский край, город Барнаул, проспект Ленина, дом 61
- ФИО
- Бочаров Сергей Николаевич (Руководитель)
- E-mail адрес
- rector@asu.ru
- Контактный телефон
- +7 (385) 2291291
- Сайт
- https://www.asu.ru/