РАСПОЗНАВАНИЕ ЧАСТИЧНОЙ ВЫПУКЛОСТИ ОБЪЕДИНЕНИЯ НЕСКОЛЬКИХ МНОГОГРАННЫХ МНОЖЕСТВ

Работа посвящена алгоритмическим аспектам частичной выпуклости, являющейся обобщением классического понятия выпуклости. Понятие частичной выпуклости часто необходимо вводить при изучении многих прикладных проблем, таких как задачи синтеза СБИС, обработки изображений, проектирования баз данных и др., поскольку требование традиционной выпуклости слишком ограничительно. В то же время частичная выпуклость сохраняет многие полезные свойства классической выпуклости, что позволяет находить эффективные алгоритмы для их решения. В настоящей статье исследуется проблема распознавания частичной выпуклости для объединения нескольких многогранных множеств, заданных в виде пересечений полупространств в n-мерном линейном пространстве. Нами установлен необходимый и достаточный признак частичной выпуклости для объединения многогранных множеств. Используя данный признак частичной выпуклости, в случае конечности множества направлений частичной выпуклости нами разработан полиномиальный алгоритм распознавания для объединения нескольких многогранных множеств, заданных пересечениями полупространств, при условии, что число этих множеств фиксировано. Отметим, что ранее для рассматриваемой задачи был известен полиномиальный алгоритм ее решения только для случая объединения двух многогранных множеств.

1. Rawlins, G. Ortho-convexity and its generalizations / G. Rawlins, D. Wood // Machine Intelligence and Pattern Recognition. – Amsterdam: North-Holland, 1988. – P. 137–152.

2. Найденко, В. Г. Частичная выпуклость / В. Г. Найденко // Мат. заметки. – 2004. – Т. 75, вып. 2. – C. 222–235.

3. Найденко, В. Г. Распознавание частичной выпуклости объединения многогранных множеств / В. Г. Найденко // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2006. – № 4. – С. 45–49.

4. Bemporad, A. Convexity recognition of the union of polyhedral / A. Bemporad, K. Fukuda, F. D. Torrisi // Comput. Geometry. – 2001. – Vol. 18, № 3. – P. 141–154.

5. The explicit linear quadratic regulator for constrained systems / A. Bemporad [et al.] // Automatica. – 2002. – Vol. 38, № 1. – P. 3–20.

6. Препарата, Ф. Вычислительная геометрия: пер. с англ. / Ф. Препарата, М. Шеймос. – М.: Мир, 1989. – 478 с.

7. Метельский, Н. Н. Алгоритмические аспекты частичной выпуклости / Н. Н. Метельский, В. Г. Найденко // Мат. заметки. – 2000. – Т. 68, вып. 3. – C. 399–410.