%0 article
%A Найденко В. Г., 
%T РАСПОЗНАВАНИЕ ЧАСТИЧНОЙ ВЫПУКЛОСТИ ОБЪЕДИНЕНИЯ НЕСКОЛЬКИХ МНОГОГРАННЫХ МНОЖЕСТВ
%D 2018
%R 10.29235/1561-2430-2018-54-1-38-43
%J Известия Национальной академии наук Беларуси. Серия физико-математических наук
%X Работа посвящена алгоритмическим аспектам частичной выпуклости, являющейся обобщением классического понятия выпуклости. Понятие частичной выпуклости часто необходимо вводить при изучении многих прикладных проблем, таких как задачи синтеза СБИС, обработки изображений, проектирования баз данных и др., поскольку требование традиционной выпуклости слишком ограничительно. В то же время частичная выпуклость сохраняет многие полезные свойства классической выпуклости, что позволяет находить эффективные алгоритмы для их решения. В настоящей статье исследуется проблема распознавания частичной выпуклости для объединения нескольких многогранных множеств, заданных в виде пересечений полупространств в n-мерном линейном пространстве. Нами установлен необходимый и достаточный признак частичной выпуклости для объединения многогранных множеств. Используя данный признак частичной выпуклости, в случае конечности множества направлений частичной выпуклости нами разработан полиномиальный алгоритм распознавания для объединения нескольких многогранных множеств, заданных пересечениями полупространств, при условии, что число этих множеств фиксировано. Отметим, что ранее для рассматриваемой задачи был известен полиномиальный алгоритм ее решения только для случая объединения двух многогранных множеств.
%U https://www.academjournals.by/publication/12912