RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления // Архив

Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр., 2019, том 15, выпуск 4, страницы 592–602 (Mi vspui431)

Информатика

The problem of a maximal weighted area of axis-parallel rectangle that covers polygons

[Задача покрытия полигонов прямоугольной областью с максимальным весом]

L. V. Shchegolevaa, R. V. Voronova, L. Sedovb

a Petrozavodsk State University, 33, Lenina pr., Petrozavodsk, 185910, Russian Federation
b Linköping University, Department of Science and Technology, Campus Norrköping, 33, Bredgatan, 60221, Norrköping, Sweden

Аннотация: Представлена задача поиска оптимального расположения прямоугольника с максимальной взвешенной площадью. Размеры прямоугольника заданы, стороны прямоугольника параллельны осям координат. На плоскости расположены несамопересекающиеся полигоны произвольной формы с заданной плотностью. Взвешенная площадь прямоугольника рассчитывается как суммарная площадь частей полигонов, накрытых прямоугольником, умноженных на плотность. Описан алгоритм решения задачи. Такая задача возникает при определении мест рубок леса, когда планируемая лесосека может быть смоделирована прямоугольником, а полигоны описывают таксационные выделы лесного фонда, для каждого из которых известен запас леса на 1 га.

Ключевые слова: задача максимизации взвешенной площади, полигоны.

УДК: 519.8

MSC: 90B85

Поступила: 29 апреля 2019 г.
Принята к печати: 7 ноября 2019 г.

Язык публикации: английский

DOI: 10.21638/11701/spbu10.2019.414



© МИАН, 2024