vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2018-54-1-38-43vestifm-296Research ArticleМАТЕМАТИКАMATHEMATICSРАСПОЗНАВАНИЕ ЧАСТИЧНОЙ ВЫПУКЛОСТИ ОБЪЕДИНЕНИЯ НЕСКОЛЬКИХ МНОГОГРАННЫХ МНОЖЕСТВDIRECTIONAL CONVEXITY RECOGNITION OF THE UNION OF SEVERAL POLYHEDRAНайденкоВ. Г.NaidenkoV. G.

кандидат физико-математических наук, ведущий научный сотрудник

Ph. D. (Physics and Mathematics), Leading Researcher

naidenko@im.bas-net.byИнститут математики Национальной академии наук Беларуси, МинскInstitute of Mathematics of the National Academy of Sciences of Belarus2018050420185413843Copyright © Найденко В.Г., 20182018Найденко В.Г.Naidenko V.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/296

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

The article is devoted to the algorithmic aspects of partial convexity, which is a generalization of the classical concept of convexity. Often, it is necessary to introduce the concept of partial convexity when studying many applied problems such as problems of VLSI design, image processing, database design, etc., since the requirement of traditional convexity is too restrictive for such problems. At the same time, the partial convexity preserves many useful properties of classical convexity, which makes it possible to find effective algorithms for solving these problems. A problem for recognizing directional convexity of the union of polyhedral sets in the n-dimensional linear space is investigated. We have established a necessary and sufficient attribute of the partial convexity for the union of polyhedral sets. Using this attribute of partial convexity, in the case of the finiteness of the set of directions of partial convexity, we have developed a polynomial recognition algorithm for the union of several polyhedral sets given by intersections of half-spaces, provided that the number of these sets is fixed. We note that earlier for the problem under consideration, a polynomial algorithm for solving it was known only for the case of the union of two polyhedral sets.

выпуклостьобобщенная выпуклостьчастичная выпуклостьзадача распознавания выпуклостивычислительная сложностьconvexitygeneralized convexityrestricted-orientation convexityproblem to recognize convexitycomputational complexityReferencesRawlins, G. Ortho-convexity and its generalizations / G. Rawlins, D. Wood // Machine Intelligence and Pattern Recognition. – Amsterdam: North-Holland, 1988. – P. 137–152.Rawlins G., Wood D. Ortho-convexity and its generalizations. Machine Intelligence and Pattern Recognition. Am ster-dam, North-Holland, 1988, pp. 137–152. Doi: 10.1016/b978-0-444-70467-2.50015-1Найденко, В. Г. Частичная выпуклость / В. Г. Найденко // Мат. заметки. – 2004. – Т. 75, вып. 2. – C. 222–235.Naidenko V. G. Partial convexity. Mathematical Notes, 2004, vol. 75, no. 1–2, pp. 202–212. Doi: 10.1023/b:matn. 0000015036.94515.c0Найденко, В. Г. Распознавание частичной выпуклости объединения многогранных множеств / В. Г. Найденко // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2006. – № 4. – С. 45–49.Naidenko V. G. Directional convexity recognition of the union of polyhedra. Vestsі Natsyianal’nai akademіі navuk Belarusі. Seryia fіzіka-matematychnykh navuk = Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics series, 2006, no. 4, pp. 45–49 (in Russian).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.Bemporad A., Fukuda K., Torrisi F. D. Convexity recognition of the union of polyhedral. Computational Geometry, 2001, vol. 18, no. 3, pp. 141–154. Doi: 10.1016/s0925-7721(01)00004-9The explicit linear quadratic regulator for constrained systems / A. Bemporad [et al.] // Automatica. – 2002. – Vol. 38, № 1. – P. 3–20.Bemporad A., Morari M., Dua V., Pistikopoulos E. N. The explicit linear quadratic regulator for constrained systems. Automatica, 2002, vol. 38, no. 1, pp. 3–20. Doi: 10.1016/s0005-1098(01)00174-1Препарата, Ф. Вычислительная геометрия: пер. с англ. / Ф. Препарата, М. Шеймос. – М.: Мир, 1989. – 478 с.Preparata F. P., Shamos M. I. Computational Geometry. Springer-Verlag, 1985. 400 р. Doi: 10.1007/978-1-4612-1098-6Метельский, Н. Н. Алгоритмические аспекты частичной выпуклости / Н. Н. Метельский, В. Г. Найденко // Мат. заметки. – 2000. – Т. 68, вып. 3. – C. 399–410.Metel’skii N. N., Naidenko V. G. Algorithmic aspects of partial convexity. Mathematical Notes, 2000, vol. 68, no. 3, pp. 345–354. Doi: 10.1007/bf02674558

The authors declare that there are no conflicts of interest present.