Обобщенно-выпуклые оболочки и аппроксимации геометрических объектов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

о

* 0 «

АКАДЕМИЯ НАУК РЕСПУБЛИКИ БЕЛАРУСЬ ИНСТИТУТ МАТЕМАТИКИ

УДК 519.85

МАРТЫИЧИК ВИКТОР НИКОЛАЕВИЧ

ОБОБЩЁННО-ВЫПУКЛЫЕ ОБОЛОЧКИ И АППРОКСИМАЦИИ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ

01.01.09 — математическая кибернетика

Автореферат диссертации на соискание учёной степени кандидата физико-математических паук

Минск - 1990

Работа выполнена в Институте математики Академии наук Беларуси

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

профессор МЕТЕЛЬСКИЙ H.H.

Официальные оппоненты: доктор физико-математических наук,

профессор СОТСКОВ Ю.Н.

кандидат физико-математических наук, додент ПИСАРУК Н. Н. •

Оппонирующая организация: Вычислительный центр РАН

Защита состоится " 15" geKO-Spff 199G г. в "_17п часов на заседании совета по защите диссертаций Д 01.02.02 в Институте математики АН Беларуси по адресу: 220072, г. Минск, ул. Сурганова, 11.

С диссертацией можно ознакомиться в библиотеке Института математики АН Беларуси.

Автореферат разослан 199G года.

Учёный секретарь совета по защите диссертаций кандидат физ.-мат. наук

А. И. Астровский

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

Во введении даётся краткая оценка современного состояния проблемы, рассматриваемой в диссертации.

В первой главе приведён краткий обзор полученных до настоящего времени результатов. Дано понятие классически выпуклой оболочки, используемой в целях аппроксимации. Отмечены наиболее эффективные алгоритмы вычисления указанной оболочки конечного множества точек и простого многоугольника на плоскости. Приведены наиболее существенные результаты теории ö-выпуклости, среди которых следует отметить теоремы отделимости и декомпозиции (Роулинс, Вуд, 1989), построение О-выпуклой оболочки конечного множества точек в случае двух осеориентированных направлений (Оттман, Соисалон-Сойнинен, Вуд, 1984), вычисление (9-выпуклой оболочки С-ориентирован-пого многоугольника (Роулинс, Вуд, 1987). Однако все эти результаты относятся к двумерному случаю. Только в 1995 г. H.H. Метсльский впервые приступил к исследованию теоретических основ частичной выпуклости в многомерном случае. Им выделено и исследовано семейство семипространств частичной выпуклости, которое охватывает всю совокупность семипространств классической выпуклости.

Вторая глава диссертации посвящен а дальнейшему теоретическому исследованию частичной выпуклости в JÍ". Здесь, в частности, впервые введено понятие конуса направлений выпуклости, которое может быть использовано для определения мер выпуклости множеств в задачах распознавания образов, обработки изображений, компьютерной графики.

Пусть О — некоторое множестпо единичных векторов (нап-

с

равлепий) вещественного л-мерного линейного пространства Нп. Прямая I называется О-щммои, если некоторый направляющий вектор прямой I принадлежит О. Множество А' С Л" называется выпуклым относительно О (О-выпуклым, частично-выпуклым), если пересечение Аг с произвольной С-прямой пусто либо связно. Обозначим через £>г>(X) множество всех единичных векторов и таких, что для любой точки а;0 € Я" прямая х = 10 + Аи, А € /? имеет пустое либо связное пересечение с Л". Для любого X множество .Ог>(Л') симметрично. Множество К(Х) = {Аи 6 Л" : V € 2?гг(Х), А > 0} называется конусом направлении выпуклости для X.

В разделе 2.1 получено описание этого конуса для произвольного замкнутого множества Аг С В", комбинирующее понятия локального и глобального конусов в точках границы X. Вектор v ф 0 называется локальным направлением для множества X С Л" в точке .г € Л', ссли существует е > 0 такое, что для любого 5 > 0,6 < точка а- + ¿г> € -V. Множество всех локальных направлений в точке х € А* называется локальным конусом в х £ X и обозначается через Ьх(Х).

Пз'сть х 6 А' С Л". Минимальный конус (31(АГ) такой, что множество з:+ (?!•(А') содержит X называется глобальным конусом множества Л" и точке х.

Пусть ЪгА' — граница множества X.

Теорема 2.1. Для замкнутого множества А' С Я'1 имеет место соотношение

Л-(Л') = Л»\( и Сх(Х)\Ьх(Х)).

а-еьг Л'

В разделе 2.2 для двумерного случая разработан алгоритм вычисления конуса направлении выпуклости простого многоугольника на плоскости.

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

ного списка вершин в соответствии с обходом границы Р по часовой стрелке. Совокупность рёбер многоугольника между последовательными выпуклыми вершинами и и v, упорядоченными в соответствии с избранным направлением обхода граничного контура назовём вогнутой -¡¡елью CU|„. Установлена взаимосвязь между конусом К(Р) и структурой границы многоугольника Р в виде следующей теоремы.

Теорема 2.2. Пусть Ch — совокупность всех вогнутых цепей многоугольника Р. Тогда справедливо соотношение

К(Р)= р) K(CU,V).

На основании этой теоремы разработан алгоритм вычисления конуса К(Р) с временной 0(?tlogn) и емкостной О(п) сложностями, где п — число вершин Р. Cj'Tb алгоритма состоит в последовательном просмотре вершин Р с целью нахождения его вогнутых цепей. Для каждой из этих цепей определяется конус её направлений выпуклости. Для нахождения требуемого конуса А"(Р) необходимо вычислить пересечение всех найденных конусов.

Третья глава диссертации посвящена дальнейшему исследованию вычислительных аспектов частичной выпуклости в Я2, а именно, построению частично-выпуклых оболочек и аппроксимаций ограниченной сложности конечного множества точек на плоскости. Здесь без ограничения общности пх>едполагается, что О является симметричным конечным множеством, т. е. О = —О, и все основные результаты главы получены при условии, что множество О направлений отсортировано по возрастанию углов, образуемых ими с положительным направлением оси X.

В разделе 3.1 вводится понятие СО-выпуклой оболочки множества X (СОН(Х)) как наименьшего классически выпуклого содержащего А' многоугольника, направления сторон которого принадлежат множеству О (рис. 1). На основании классически выпуклой оболочки конечного .множества точек Л' для конечного О получен алгоритм построения оболочки СОН(Х), требующий 0(|A"| log |А'| + \0\) времени и 0(|Л*| + |Oj) памяти и ис-

пользующий понятия опорной (9-полуплоскости, антиподальных

Следует отметить, что О-выпуклые множества могут быть очень сложными по форме и, поэтому, использование С?-выпуклой оболочки в качестве внешней аппроксимации часто бывает невозможным даже в Л2. В связи с этим, в разделе 3.2 рассматривается более пригодный в целях аппроксимации подкласс (9-выпуклости — ОС-выпуклость..

В определении ОС-выпуклости важную роль играют классически выпуклые конусы. Под выпуклым конусом мы понимаем множество С, содержащее Ах + /ху, для любых х,у £ С и любых неотрицательных А и /¿. Выпуклый конус С называется острым, если С не содержит одномерных подпространств, т. е. х 6 С и —х 6 С влечёт х = 0. Выпуклая коническая оболочка СН(Х) множества X■ есть наименьший выпуклый конус, содержащий X.

Конус С называется О -конусом, если С является выпуклой конической оболочкой некоторого подмножества С.

Пусть а 6 Л2 и С есть максимальный острый О-конус. Множество с1(7?2 \ (а + С)) называется базовым О -конусом в точке а, где с1Х — замыкание множества X. Базовый О-конус А в точке а называется опорным к множеству X, если X С А и каждая из сторон конуса А \ а имеет хотя бы одну общую точку с X.

Пересечение всех базовых О-конусов, содержащих множество Л" С Л2, называется ОС-выпуклой оболочкой X и обозначается ОСН(Х) (см. рис. 1). ОС-выпуклые множества Аг определяются, как обычно, с помощью равенства ОСН(Х) = Аг.

В этом разделе для конечных X и О введено понятие корнера, как множества СОН(Х)\А, где 'А — опорный базозый О-конус Аг (см. рис. 1). Установлены некоторые свойства корнеров, необходимые для построения ОС-выпуклой оболочки, осуществляемого на основании следующей теоремы.

Теорема 3.3. Пусть К — совокупность всех корнеров множества X.Тогда

ОСН{X) = СОН{Х) \ и т.

тек

Разработан алгоритм вычисления ОС-выпуклой оболочки конечного множества X, требующий 0(|АГ| 1о§ |А'| + |0|) времени и 0(\Х\ + |0|) памяти.

В разделе 3.3 О-выпуклая оболочка множества X (ОН(Х)) определяется как минимальное по включению О-выпуклое множество, содержащее А'. Отметим наличие существенных трудностей при построении О-выпуклой оболочки несвязных множеств. Это связано с тем, что теорема декомпозиции ориентаций (Роу-линс, Вуд, 19Б9) даёт естественный подход для вычисления указанной оболочки только связного множества X С Я2, но неверна в случае, когда множество несвязно. Тем не менее в этом разделе разработан алгоритм вычисления О-выпуклой оболочки копечного множества А' точек на плоскости, опирающийся на следующую теорему.

Теорема 3.5. Пусть О — конечное множество направлений. Тогда все ОС-выпуклые множества в Я2 являются О-выпуклыми. Любое замкнутое связное О-выпуклое множество в Я2 является ОС-выпуклым.

Из теоремы 3.5 следует, что для замкнутых связных множеств X С К2 О-выпуклая оболочка А" совпадает с ОС-выпуклой оболочкой.

Алгоритм вычисления О-выпуклой оболочки состоит из двух

частей: определения подмножеств X (кластеров), которые формируют максимальные компоненты связности ОН(Х), и построения границы ОН(X) на основе вычисления ОС-выпуклых оболочек кластеров.

Теорема 3.6. Пусть X и О — конечные множества точек и направлений на плоскости. О-выпуклую оболочку множества Л' можно вычислить за время 0(|А| |ü| log |АГ|) с использованием 0(|А'||0|) памяти.

Раздел 3.4 посвящен ОС-выпуклым внешним аппроксимациям конечного множества X точек с априорным ограничением на число корнеров. ОС-выпуклой внешней аппроксимацией ОСА(Х) называется ОС-выпуклое множество, получаемое из оболочки СОН(Х) путём удаления некоторого числа корнеров. Число корнеров ОСА(X) называется рангом аппроксимации. Ставится следующая аппроксимационная задача (A3): для заданных конечных множеств X и Ö и неотрицательного целого числа г определить аппроксимацию ОСА(Х) минимальной площади ранга не более г. Задача A3 сводится к задаче нахождения в взвешенном бесконтурном ориентированном графе пути, содержащего не более г дуг и имеющего наибольшую сумму bccod этих дуг, для которой известен алгоритм типа динамического программирования с временной сложностью O^'IV)2), где V — число вершин графа.

Теорема 3.8. Задачу A3 можно решить с помощью алгоритма временной 0(г|Х|2+ \0\) и емкостной 0(г|Х| + )С|) сложности.

Четвёртая глава диссертационной работы посвящена дальнейшему развитию аппарата обобщённой выпуклости изотетичес-ких областей. Здесь рассматривается существенно новый класс обобщённой выпуклости — S-выпуклость, впервые введённый H.H. Метельским в 1991 г. В этой главе приведены как теоретические результаты исследования свойств 5-выпуклости, так и алгоритмы построения 5-выпуклых оболочек и аппроксимаций.

В разделе 4.1 осеориептироваппый прямоугольник определяет-

ся системой неравенств

а < х < Ь с < у < (1,

где а < Ь, с < с1 — фиксированные действительные числа.

Изогпегпическая область (I-область) — подмножество евклидовой плоскости Е2, представимое в виде конечного объединения невырожденных осеориентированных прямоугольников.

Полубесконечная осеориентированная полоса, получаемая заменой только одного из элементов а,Ь, с, с! в приведённой выше системе на оо, называется изотетической зоной (I-зоной), а замыкание её дополнения — базовой 1-зопой. Выпуклый конус, граница которого образуется парой осеориентированных лучей при замене на оо элементов только одной из пар (а,с), (а,с1), (£>, с), (Г), называется пзотегпическим конусом (I-%071усам), а замыкание его дополнения — базовым I -конусом. Следует отметить, что базовый /-конус является базовым 0-конусом, если множество О представлено двумя осеориентированными направлениями.

Минимальный по включению о се ориентировано ый прямоугольник, содержащий /-область И С Е2, называется Я-оболочкой £> и обозначается ЯН(О) (рис. 2).

й

Рис.2 I- и 5-оболочки изотетической области Г>. ЯН(И) — аЪсс!. иии2, и3, Щ, иг„ ¿7«, и7, и,}, ию, ип — сайдеры.

~ /¿-сайдеры. и4, и5,Щ,ио, г/ю, ^и — о-сайдеры.

а

Пересечение всех базовых /-конусов (/-зон), содержащих /-обласхь В С Е2, называется I-оболочкой (Б-оболочкой) И и обозначается 1Н{В) (¿Я(£>)) (см. рис. 2).

Прямоугольник и называется сайдсром I-области D, если II есть максимальный осеориентированный прямоугольник, содержащийся в области /?//(£)) \ Б и имеющий непустое пересечение с границей КН(Б). Если это пересечение содержит вертикальный (горизонтальный) отрезок границы /1-оболочки, то II является Л-сайдером (у-сайдером) (см. рис. 2).

Доказано, что ¿-оболочка /-области /) получается удалением из её Е-оболочки всех сайдеров. Определены /г- (/»//(£>)) и и-оболочки (уН(О)) /-области £>, получаемые, соответственно, удалением всех и и-сайдеров. Установлены некоторые соотношения между оболочками изотетических областей в виде последовательности включений

В С ¿Я(£>) С ЬЯ(Б)(«Я(1>)) С /Яф) С ЯЯ(Д).

Доказана следующая теорема.

Теорема 4.5. Для /-области О справедливо соотношение

5Я(Л) = «/(£>) р) !>//(£>).

Раздел 4.2 посвящен построению ¿-оболочек изотетических областей. Здесь для произвольной /-области с Аг вершинами разработан алгоритм вычисления /¿- и и-оболочек с временной и емкостной 0(íN) сложностями, в основе которого лежит метод плоского заметания. На основании этого алгоритма и теоремы 4.5 предложен алгоритм вычисления ¿-обо-лочки произвольной области, требующий N + р) времени и 0(Аг+р) памяти, где р — число вершин ¿-оболочки.

Следует отметить, что число вершин ¿-оболочки изотетиче-ской области может существенно превышать число вершин самой области, причём даже в том случае, когда область является связной. Тем не менее для связной /-области в разделе 4.2 получен, линейный от числа её вершин алгоритм вычисления ¿-оболочки.

В разделе 4.3 решена задача вычисления 5-выпуклой аппроксимации ограниченной сложности. Аппроксимацией LHr{D) ограниченной сложности г Г-области D с N вершинами называется наименьшая по площади S-выпуклая /-область, содержащая D и имеющая не более г вершин. Установлены некоторые свойства границы LHr(D). В частности, показано, что вершины LHr(D) принадлежат конечному множеству точек МР, расположенных в области RH(D)\h\tD, где int D — внутренность I-области D. Доказано, что граница аппроксимации ограниченной сложности состоит из цепей, монотонных относительно горизонтальной и вертикальной прямой. Вычисление аппроксимации LHT(D) основывается на принципах динамического программирования. Сначала множество точек МР нумеруется определённым образом. Затем в процессе прямого хода динамического программирования для каждой точки р,- € МР вычисляется некоторая величина Ft[pi), максимально сокращающая площадь LHr(D). Каждая величина Ft(pi) помечается определённым образом. Далее среди величин Ft(pj), где pj — точки некоторого подмножества из МР, выбирается максимальная Ft(pm). В результате обратного хода динамического программирования, начиная от точки рт, по сделанным пометкам величин Ft(pi) определяются вершины границы LHr(D).

Теорема 4.10. Аппроксимация ограниченной сложности г I-области с N вершинами может быть вычислена за время 0(rN3) при затратах памяти 0(rN2).

ВЫВОДЫ

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

1. Описан конус направлений выпуклости замкнутых множеств в Л".

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

3. Получены эффективные алгоритмы построения частично-выпуклых оболочек, а именно, СО-, ОС- и 0-выпуклых оболочек, конечного множества точек в Л2.

4. Построен алгоритм вычисления ОС-выпуклой внешней аппроксимации с априорным ограничением на число корнеров исходного множества.

5. Исследованы основные свойства существенно нового класса обобщённой выпуклости — 5-выпуклости.

6. Разработаны эффективные алгоритмы построения ¿'-оболочек произвольной и связной изотетпческих областей.

7. Решена задача вычисления 5-выпуклой аппроксимации наименьшей площади с числом вершин, ограниченным некоторой константой.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В РАБОТАХ

[1] Метельский H.H., Мартынчик В. Н. Основные классы обобщённой выпуклости для изотетических областей.— Препринт / Ин-т математики АН БССР.- Минск, 1991.- СО с.

[2] Азаренок A.C., Мартынчик В. П., Метельский H.H. Вычисление обобщённо-выпуклых аппроксимаций планарных геометрических объектов // Журн. вычис. ма-т. и мат. физики.-1993 - Т. 33, N 12,- С. 1879-1893.

[3]. Мартынчик В. Н. Вычисление внешних аппроксимаций специальных классов областей // Актуальные проблемы информатики: математическое, программное и информационное обеспечение: Тез. докл. конф,- Минск, 1994.- С. 200-201.

[4] Мартынчик В.Н. Вычисление внешних аппроксимаций изотетических областей // Известил АН Беларуси. Сер. физ.-мат. наук - 1995,- N 2,- С. 97-101.

[5] Мартынчик В.Н. Конус направлений выпуклости // Автоматизация проектирования дискретных систем: Тез. докл. конф - Минск, 1995 - С. 12С.

[G] Мартынчик В. II. Конус выпуклых направлений многоугольной области // Известия АН Беларуси. Сер. физ.-мат. наук.-1996 - N 3.- С. 93-97.

[7] Метельский Н. Н., Мартынчик В. Н. Частичная выпуклость // Математические заметки.- 199G.- Т. G0, N 3,- С. 406-413.

[8] Метельский H.H., Мартынчик В.Н. Конус направлений выпуклости замкнутых множеств в В" // Доклады АН Беларуси.- 199G.- N 3 - С. 19-21.

[9] Martynchik V., Metelski N., Wood D. (9-convexity: computing hulls, approximations, and orientation sets.- Technical Report HKUST-CS96-23 / The Hong Kong University of Science & Technology, 1996 -6 p.

[10] Martyncliik V., Metelski N., Wood D. C-convexity: computing hulls, approximations, and orientation sets // Proceedings of the Eighth Canadian Conference on Computational Geometry.- Ottawa, Canada, 199G- P. 2-7.

РЕЗЮМЕ Мартынчик Виктор Николаевич "Обобщённо-выпуклые оболочки и аппроксимации геометрических объектов"

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

Диссертация посвящена развитию идей и понятий обобщённой частичной выпуклости и дальнейшей разработке математического аппарата аппроксимации сложных геометрических объектов менее сложными по форме. Основные результаты работы:

— получено описание конуса направлений лыпуклости замкнутых множеств в Я" и разработан алгоритм вычисления этого конуса для многоугольных областей на плоскости;

— разработаны эффективные алгоритмы построения частично-выпуклых оболочек, а именно, СО-, ОС- и (9-вынуклых оболочек, конечного множества точек в Я2;

— введено понятие ОС-выпуклой внешней аппроксимации конечного множества точек на плоскости и построен алгоритм её вычисления;

— исследованы свойства существенно нового класса обобщённой выпуклости (5-выпуклости) и разработаны эффективные алгоритмы построения 5-оболочек произвольной и связной изоте-тических областей;

— решена задача вычисления 5-выпуклой аппроксимации наименьшей площади с числом вершин, ограниченным некоторой константой.

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

РЭЗЮМЭ Мартынчык Вштар 1\Пкаласв1ч "Абагульнена-выпуклыя абалоша 1 апракЫмацьн геаметрычных аб'ектау"

Ключавыя словы: абагульненая выпукласць, абалонка, апрак-амацыя, конус напрамкау выпукласщ, ¡затэтычная вобласць.

Дысертацыя прысвечана развщцю ¡дэй 1 паняццяу абагульне-най частковай выпукласщ 1 далейшай распрацо^цы матэматычна-га апарата апраксшацьи складаных геаметрычных аб'ектау менш складаныли па форме. Асноуныя вынш прады:

— атрымана ашсанне конуса напрамкау выпукласщ замкнутых мноства^ у Л" 1 распрацаваны алгарытм выл^чэння гэтага конуса для многавугольных абласцей на плоскасщ;

— распрацаваны эфектыуныя алгарытмы пабудовь* часткова-выпуклых абалонак, а ¡менна, СО-, ОС- 1 О-выпуклы:: абалонак, канечнага мноства пункта^ у Л2;

— уведзена паняцце С?С-выпуклай знешняй апрак^мацьп канечнага мноства пунктау на плоскасщ I пабудаваны алгарытм яе выл1чэння;

— даследаваны уласщвасщ 1стотна новага класа абагульне-най выпукласщ (5-выпукласщ) 1 распрацаваны эфектыу'ныя алгарытмы пабудовы 5-абалонак адвольнай 1 звязнай ¡затэтычных абласцей;

— рашана задача выл1чэння 5-выпз'клай апракс!мацьп най-меншай плошчы з л!кам вяршынь, абмежаваным нейкай канстан-тай.

Ашсанне конуса напрамкау выпукласщ 1 алгарытм яго вы-л1чэння даюць магчымасць вызиачэння мер выпукласщ мност-ва^ 1 могуць быцъ выкарыстаны у задачах распазнавання во-бразау, апрацоущ адлюстраванняу, камп'ютэрнай графщы. Рас-працаваныя алгарытмы пабудовы абагульнена-выпуклых абалонак I апракамацый мносхвау пунктау на плоскасщ 1 ¡затэтычных абласцей могуць выкарыстоувацца у задачах размяшчэння блокау ЗВ1С 1 кампанснт ЭВМ. раскрою матэрыялау, упакоуы грузау, распрацоуы робататэхшчных астэм, праектавання баз даных.

SUMMARY Martyncliik Victor Nikolaevich "Generalized convex hulls and approximations of geometric objects"

Key words: generalized convexity, Lull, approximation, cone of convexity directions, isothetic polygon.

The thesis is devoted to investigation of ideas and notions of generalized partial convexity and developing mathematical means for approximation of complex geometric objects.

Main results of the dissertation are:

— the cone of convexity directions for closed sets in Rn is described; an algorithm for computing the cone for a polygonal region on the plane is developed;

— effective algorithms for constructing the partially convex hulls of a finite point set in R2, in particular, C'O-, OC- and O-convex hulls, are developed;

— a notion of outer (9C-convex approximation for a finite point set is introduced and ail algorithm for its calculation is proposed;

— some characteristics of new class of generalized convexity (S-convexity) are investigated and effective algorithms for constructing S-liulls for arbitrary and connected isothetic polygons are developed;

— problem of computing of a 5-convex approximation of the smallest area with the number of vertices bounded by some constant is solved.

The description of the cone of convexity directions and an algorithm for its computing give rise to determining of convexity measures and can be used for pattern recognition, image processing, and computer graphics. The algorithms for constructing generalized convex hulls and approximations of a point set on the plane and isothetic polygons can be used for placement of VLSI blocks, cutting stock problems, packing containers, database design.

7X /J'