О некоторых вариациях задач об охране картинной галереи
Видеокамеры являются наиболее распространенным и доступным средством охраны. То, что попадает в объектив камеры, передается на экраны мониторов в помещении охраны. Важно, чтобы количество мониторов было сведено к минимуму, при этом камеры должны размещаться таким образом, чтобы все помещение находил...
Main Authors: | , , |
---|---|
Format: | Article |
Language: | English |
Published: |
Altai State University
2024-04-01
|
Series: | Известия Алтайского государственного университета |
Subjects: | |
Online Access: | http://izvestiya.asu.ru/article/view/15009 |
_version_ | 1797216058602422272 |
---|---|
author | Александр Владимирович Гринкевич Дмитрий Николаевич Оскорбин Егор Дмитриевич Титов |
author_facet | Александр Владимирович Гринкевич Дмитрий Николаевич Оскорбин Егор Дмитриевич Титов |
author_sort | Александр Владимирович Гринкевич |
collection | DOAJ |
description | Видеокамеры являются наиболее распространенным и доступным средством охраны. То, что попадает в объектив камеры, передается на экраны мониторов в помещении охраны. Важно, чтобы количество мониторов было сведено к минимуму, при этом камеры должны размещаться таким образом, чтобы все помещение находилось под охраной. Уменьшение числа видеокамер позволяет уменьшить цену всей системы наблюдения. Оптимизации систем защиты посвящена серия задач об охране картинной галереи. В настоящее время задачи об охране картинной галереи являются достаточно хорошо изученными задачами видимости в вычислительной геометрии. Они возникли как задачи охраны некоторой художественной галереи наименьшим числом средств наблюдения, которые обозревают все ее залы. В двумерном случае план галереи представлен в виде простого многоугольника, охранник — точкой внутри него.
В данной работе рассматриваются две вариации задачи: проблема сторожевого маршрута и задача об охране картинной галереи на поверхности выпуклого многогранника. Эти задачи рассматривались в работах многих математиков. Нами приводятся описание алгоритмов решения этих задач и псевдокоды основных процедур, необходимых для реализации этих алгоритмов на языке программирования Python. |
first_indexed | 2024-04-24T11:39:56Z |
format | Article |
id | doaj.art-d9ba64eca2e34acc9fe08aabe88f5ea7 |
institution | Directory Open Access Journal |
issn | 1561-9443 1561-9451 |
language | English |
last_indexed | 2024-04-24T11:39:56Z |
publishDate | 2024-04-01 |
publisher | Altai State University |
record_format | Article |
series | Известия Алтайского государственного университета |
spelling | doaj.art-d9ba64eca2e34acc9fe08aabe88f5ea72024-04-10T02:39:03ZengAltai State UniversityИзвестия Алтайского государственного университета1561-94431561-94512024-04-011(135)10110710.14258/izvasu(2024)1-1415009О некоторых вариациях задач об охране картинной галереиАлександр Владимирович Гринкевич0Дмитрий Николаевич Оскорбин1Егор Дмитриевич Титов2Алтайский государственный университет, Барнаул, РоссияАлтайский государственный университет, Барнаул, РоссияАлтайский государственный университет, Барнаул, РоссияВидеокамеры являются наиболее распространенным и доступным средством охраны. То, что попадает в объектив камеры, передается на экраны мониторов в помещении охраны. Важно, чтобы количество мониторов было сведено к минимуму, при этом камеры должны размещаться таким образом, чтобы все помещение находилось под охраной. Уменьшение числа видеокамер позволяет уменьшить цену всей системы наблюдения. Оптимизации систем защиты посвящена серия задач об охране картинной галереи. В настоящее время задачи об охране картинной галереи являются достаточно хорошо изученными задачами видимости в вычислительной геометрии. Они возникли как задачи охраны некоторой художественной галереи наименьшим числом средств наблюдения, которые обозревают все ее залы. В двумерном случае план галереи представлен в виде простого многоугольника, охранник — точкой внутри него. В данной работе рассматриваются две вариации задачи: проблема сторожевого маршрута и задача об охране картинной галереи на поверхности выпуклого многогранника. Эти задачи рассматривались в работах многих математиков. Нами приводятся описание алгоритмов решения этих задач и псевдокоды основных процедур, необходимых для реализации этих алгоритмов на языке программирования Python.http://izvestiya.asu.ru/article/view/15009максимальное паросочетаниесторожевой маршрутпростой многоугольникалгоритм расстановки охранниковразрезрефлективная вершинатриангуляциядвойственный граф многогранника |
spellingShingle | Александр Владимирович Гринкевич Дмитрий Николаевич Оскорбин Егор Дмитриевич Титов О некоторых вариациях задач об охране картинной галереи Известия Алтайского государственного университета максимальное паросочетание сторожевой маршрут простой многоугольник алгоритм расстановки охранников разрез рефлективная вершина триангуляция двойственный граф многогранника |
title | О некоторых вариациях задач об охране картинной галереи |
title_full | О некоторых вариациях задач об охране картинной галереи |
title_fullStr | О некоторых вариациях задач об охране картинной галереи |
title_full_unstemmed | О некоторых вариациях задач об охране картинной галереи |
title_short | О некоторых вариациях задач об охране картинной галереи |
title_sort | о некоторых вариациях задач об охране картинной галереи |
topic | максимальное паросочетание сторожевой маршрут простой многоугольник алгоритм расстановки охранников разрез рефлективная вершина триангуляция двойственный граф многогранника |
url | http://izvestiya.asu.ru/article/view/15009 |
work_keys_str_mv | AT aleksandrvladimirovičgrinkevič onekotoryhvariaciâhzadačobohranekartinnojgalerei AT dmitrijnikolaevičoskorbin onekotoryhvariaciâhzadačobohranekartinnojgalerei AT egordmitrievičtitov onekotoryhvariaciâhzadačobohranekartinnojgalerei |