Вычисление частично выпуклых оболочек и аппроксимаций конечных планарных множеств

Исследуются вычислительные аспекты частичной выпуклости в пространстве $\mathbb R^2$. Рассмотрены некоторые классы частичной выпуклости и соответствующие им оболочки. Для конечного множества точек разработаны эффективные алгоритмы вычисления указанных оболочек. Предложен алгоритм вычисления плотнейшей частично выпуклой внешней аппроксимаций конечного множества точек с ограничением на меру сложности ее формы. Эта аппроксимация вычисляется посредством сведения к некоторой дискретной экстремальной задаче на графе.