Обобщенно-выпуклые оболочки и аппроксимации геометрических объектов Мартынчик, Виктор Николаевич

Введение к работе

Актуальность темы диссертации. Классическая выпуклость служит основой многих фундаментальных результатов в математике. Однако, классическая выпуклость является скорее исключительным, чем характерным свойством геометрических объектов, рассматриваемых в приложениях. Естественным путём получения более общих математических результатов и расширения сферы их применения является введение аналогов и обобщений классического понятия выпуклости. Одним из естественных обобщений является так называемая частичная выпуклость (выпуклость по заданному множеству направлений, О-выпук-лость, Роулинс, Вуд, 1988). Заметим, что все результаты предшественников (Вуд, Роулинс, Сонсалон-Сойнинен, Шуирер и др.) относятся к двумерному случаю, причём большинство из них связано с алгоритмическими аспектами. Лишь недавно (1995 г.) Н.Н. Метельский впервые обратился к исследованию фундаментальных свойств частичной выпуклости в многомерном случае. В связи с проблемой описания наименьших баз пересечений О-вьгоуклых множеств им изучались семипространства частичной выпуклости в R".

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

Связь работы с крупными научными программами, темами. Работа над диссертацией проводилась в лаборатории математических проблем автоматизации проектирования и отделе математической кибернетики Института математики АН Беларуси

в соответствии с госбюджетными темами "Исследование математических проблем теории принятия решений, моделирования процессов легирования многослойных полупроводниковых структур, проблем размещения и укладки графо-геометрических систем, проектирования систолических спецпроцессоров на базе СБИС (1990-1992 гг., Постановление Президиума АН Беларуси N 147 от 6 декабря 1989 г.), "Исследование комбинаторно-геометрических структур и разработка комбинаторных алгоритмов" (1993-1995 гг., Постановление Президиума АН Беларуси N 3 от 1 декабря 1993 г.), а также на основании договора с Фондом фундаментальных исследований Республики Беларусь N Ф95-016 от 31 января 199G г. по теме "Дискретные структуры: представления, аппроксимации, оптимизация, сложностные аспекты". Цель и задачи исследования. Целью диссертации является развитие идей и понятий обобщённой частичной выпуклости и дальнейшая разработка математического аппарата аппроксимации сложных геометрических объектов. В связи v этим необходимо решить следующие задачи:

получить описание конуса направлений выпуклости замкнутых множеств в конечномерных пространствах:

разработать алгоритмы вычисления частично-выпуклых оболочек и аппроксимаций конечного множества точек на плоскости;

построить алгоритмы вычисления обобщённо-выпуклых оболочек и аппроксимаций специального класса областей, называемых изотетическими.

Научная новизна полученных результатов. Научная новизна результатов диссертации обусловлена следующим. Впервые описан конус направлении частичной выпуклости замкнутых множеств в Л" и многоугольных областей в І?², причём для плоского случая предложен алгоритм вычисления этого конуса. Дано дальнейшее развитие идей и понятий частичной выпуклости. В частности, для конечного множества точек в І?²

разработаны эффективные алгоритмы вычисления оболочек и аппроксимаций ограниченной сложности, выпуклых по заданному конечному множеств}' направлений. Дальнейшее развитие получил аппарат обобщённой выпуклости изотетических областей, характерных, прежде всего, для топологии цифровых СБИС. Проведено исследование существенно нового класса обобщённой выпуклости (^-выпуклости). Для этого класса разработаны алгоритмы вычисления S-выпуклых оболочек и аппроксимации с априорным ограничением на число вершин.

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

Экономическая значимость полученных результатов. Экономическую значимость разработанных в диссертации методов и алгоритмов оценить в настоящее время не представляется возможным.

Основные положения диссертации, выносимые на защиту.

1. Полз'чено описание конуса направлений выпуклости замкнутых множеств в R".

2. Разработан алгоритм построения конуса направлений выпуклости многоугольных областей на плоскости.

3. Исследованы три вида частично-выпуклых оболочек конечного множества точек в ІІ² и получены эффективные алгоритмы их вычисления.

4. Построен полиномиальный алгоритм вычисления плотнейшей

частично-выпз'клой аппроксимации конечного множества точек на плоскости с ограничением на мер}' сложности аппроксимации.

5. Установлены некоторые свойства и соотношение между различными видами оболочек изотетических областей, а также разработаны алгоритмы их вычисления.

6. Лля изотетических областей получен полиномиальный до сложности алгоритм вычисления двумерной обобщённо-выпуклой аппроксимации с априорным ограничением на число вершив получаемой области.

Личный вклад соискателя. Все основные результаты диссертационной работы получены автором лично. Из работ, опубликованных вместе с соавторами, в диссертацию вошли результаты, нолученные автором самостоятельно.

Апробация результатов диссертации. Результаты, вошедшие в диссертационную работу, докладывались и обсуждались на Межгосударственной научно-практической конференции творческой молодежи "Актуальные проблемы информатики: математическое, программное и информационное обеспечение" (1G-20 мая 1D94 г.. г. Минск), Международной конференции "Автоматизация проектирования дискретных систем" (15-17 ноября 1995 г., г. Минск), Международной конференции "Алгебра и математическая кибернетика", посвященной 80-летию со дня рождения академика Д. А.Супруненко (21-22 ноября 1995 г., г. Минск), 8-ой Канадской конференции по вычислительной геометрии (12-15 августа 1996 г., г. Оттава), а также на научном семинаре Института математики Технического университета г. Грац (Австрия) и семинарах в Институте математики АН Беларуси.

Опубликованность результатов. Результаты диссертации опубликованы в 10 работах.

Структура и объём диссертации. Диссертация состоит из введения, общей характеристики работы, четырёх глав, выводов и списка использованных источников из 71 наименования. Объём

диссертационной работы составляет 92 страницы машинописного текста, включая 28 рисунков.

Автор выражает искреннюю благодарность своему руководителю доктору физико-математических наук, профессору Н. Н. Ме-тельскому за внимание, проявленное к работе, за многочисленные полезные советы и замечания.