автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка и исследование эффективности алгоритмов решения больших задач вычислительной геометрии

Российская академия наук ИНСТИТУТ СИСТЕМНОГО ПРОГРАММИРОВАНИЯ

На правах рукописи УДК 681.3 513

МАРТИШИН Сергей Анатольевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РЕШЕНИЯ БОЛЬШИХ ЗАДАЧ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1996

Работа выполнена в Институте системного программирования РАН

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

Л.В.Шабанов

Официальные оппоненты:

доктор технических наук

кандидат физико-математических наук

Ю.С.Вишняков Г.С.Плесневич

Ведущая организация:

Институт высокопроизводительных вычислительных систем РАН

Защита состоится & 1996 г. в часов на заседании

диссертационного совета Д.200.50.0Гв Институте системного программирования РАН по адресу: 109004; Москва," ул. Б. Коммунистическая, д. 25

С диссертацией можно' ознакомиться в библиотеке Института! системного программирования РАН • •. ; • -

Автореферат разослан

Ученый секретарь специализированного совета Д.200.50.01

кандидат физико-математических наук

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

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

Важной составной частью вычислительной математики является вычислительная геометрия.

Предметом вычислительной геометрии являются разработка и исследование вычислительных моделей, методов и алгоритмов решения разнообразных геометрических задач при помощи ЭВМ.

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

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

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

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

Целью работы является решение двух больших задач вычислительной геометрии.

Первая задача - задача1 нахождения крайних точек для множества точек Б в с!-'мерном евклидовом'пространстве Эта задача является большой, потому что в пространствах больших размерностей выпуклая оболочка множества точек имеет сложную комбинаторную структуру. Следует заметить, что число граней политопа с N вершинами определяется величиной СНЬИ/21). '

Вторая задача - задача построения диаграммы Вороного на плоскости с ограничением, заданным простым многоугольником, для ячеек которой вычисляются различные характеристики. Эта задача является большой, так как приходится работать с большим размером входных данных, причем решение этой задачи должно выполняться в режиме реального времени.

Научная новизна работы состоит в следующем.

#

Разработан алгоритм, позволяющий решать задачу нахождения крайних точек заданного множества точек Б р ё-мерном евклидовом пространстве Её без нахождения граней выпуклой оболочки множества точек Б. Анализ каждой точки осуществляется путем решения »задачи линейного программирования (задачи ЛП). Алгоритм лЬи»-распараллеливается, так как для определения того, является ли какая-либо точка крайней достаточно знать только координаты других точек множества.

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

Практическая ценность. С помощью разработанного алгоритма нахождения крайних точек для множества точек 8 в пространстве ЕА может быть осуществлена локализация точки, то есть определено, внутри или вне выпуклой оболочки множества Б находится точка, а также решены ряд вероятностных и

СТаТИСТйЧсСКИХ ЗДЦаЧ. 1СрОмС ТОГО, ПрСДБЗрКТСЛЬНСС КалОЖДСНИС

крайних точек упрощает нахождение выпуклой оболочки.

Предложенный алгоритм построения диаграммы Вороного на плоскости с ограничением используется для решения задач, применяемых для геологического моделирования свойств залежей нефти и газа и оптимизации разведки залежей:

- интерполяция геолого-геофизических признаков;

- построение карт;

- моделирование поверхностей;

- оптимизация размещения разведочных скважин.

Апробация работы. Основные результаты работы неоднократно докладывались на семинарах в Институте проблем кибернетики РАН (1988 - 1993гг.) и в Институте системного программирования РАН (1994 - 1996гг.).

Высокая. практическая значимость решаемых задач подтверждена актами о внедрении:

1) математического и программного обеспечения в рамках темы "Решение задач нахождения оптимальных стационарных стратегий в марковских процессах принятия решений" (МГИЭМ, кафедра "Исследование операций", 2 июня 1994г.);

2) математического и программного обеспечения (ВНИГНИ, отдел 4, сектор 4.1, 29 марта 1995г.).

Публикации. Представляемые к защите результаты опубликованы в работах [1-4].

Объем и структура диссертации. Диссертация состоит из введения, трех глав и заключения. Ее общий объем 84 страницы, в.том числе 4 рисунка, 2 таблицы и список литературы из 69 наименований.

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

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

практическая значимость. Дается краткое содержание работы. • *

В первой главе рассматривается следующая задача.

Пусть в евклидовом пространстве Ed' задано множество точек

S = {рь—,рп}, содержащее N точек. Требуется определить,

является ли эти точки вершинам^ своей собственной выпуклой

оболочки, то есть найти крайние точки множества S.

В § 1.1 .дается постановка задачи и обсуждаются

существующие подходы и методы решения этой задачи.

В § 1.2 приводится оснозная теорема, используемая для

нахождения крайних точек.

Определение. Гиперплоскостью H¡ называется

гиперплоскости. d

I Ajkxk + Ajo = 0, je {l,...ri-U+l,-,n},

k=l

проходящая через точку p¡ и перпендикулярная лучу [p¡,pj), причем координаты точки Pj = {xjj,удовлетворяют условию.

I Ajkxjk + А^ < 0.

k = l

Определение. Областью £Kp¡) называется область á-мерного евклидова пространства, каждая точка которой удовлетворяет системе строгих неравенств, коэффициентами которых являются коэффициенты гиперплоскостей Hj, j = (l,...,i-l,i+l,...,n): АцХ! + Al2x2 + . . . + AldXd + Ajo > о

А<м)|Х1 + А{М)2Х2 + ... + А^.паха + А^1)0 > 0 А(1+1)1Х1 + А(Н-1)2Х2 + - + А(Н-1)Й*«1 * А(4+1)0 > о

Ап1Х1 + Ап2Х2 + . . . + АпйХй + Аао > 0.

Лемма 1. Точка р, является крайней точкой множества точек Б в (3-мерном евклидовом пространстве тогда и только тогда, когда существует область ЕКр\).

Так как гиперплоскости Н^, ) ~ (1,-..,ь1,гЧ,...,п) представляют собой пучок гиперплоскостей, то задачу определения существования области /5(р;) можно свести к задаче нахождения точки, удовлетворяющей системе нестрогих неравенств.

■ — - — — - - — Я . ■ .Я ■..... пг 1ТП№ГМг¥ Л^Л ЖШ _

дсирсмо. Л£Н1ПП11Л ^Л ^м^шип ь^^л^л/ м м

мерном пространстве можно найти за время 0(МТц>(с1,М)), уда N - число точек исходного множества, а Тц>(д,М) - время решения задачи ЛП в пространстве Ей с числом ограничений не превосходящим N.

Так как предполагается, что размерность пространства значительно меньше числа точек, то предлагается решать задачу ЛП методом Кларксона, который эффективен для данного класса задач. Для использования этого метода вводится 2ё дополнительных ограничений - по две гиперплоскости, перпендикулярные каждой координатной оси так, чтобы все точки множества Б лежали внутри многомерного параллелепипеда. Этим достигается возможность получения промежуточного оптимального решения с конечными и корректными по точности представления машинных данных координатами..

Нужно заметить, что алгоритм легко распараллеливается, так как исследовать каждую точку на принадлежность ее множеству крайних точек можно на отдельном процессоре.

§ 1.3 посвящен описанию структуры алгоритма.

Так как основной метод, использующийся при определении крайних точек - это метод линейного программирования, требующий больших затрат памяти машинного времени, то для повышения эффективности желательно решать задачу ЛП как можно меньшее число раз и с меньшим числом ограничений. Это достигается путем нахождения некотооого количества заведомо крайних (множество 5уеЛех) и заведомо внутренних точек другими способами (называемыми далее предобработками), требующими меньше времени по сравнению с решением задачи ЛП для N ограничений.

Предобработка для нахождения заведомо крайних точек позволяет достаточно быстро выявить точки этого множества Буепех, для которых з дальнейшем не будет решаться задача ЛП.

Предобработка для удаления заведомо не крайних точек с использованием кластеров гиперплоскостей решает задачу ЛП для оставшихся после предыдущей предобработки точек (множество Sunknown) с малым количеством определенным образом выбранных ограничений. Число элементов множества ^unknown» а следовательно и S может уменьшаться (множество -оставшихся после предобработки точек обозначим S*).

Предобработка для удаления заведомо не крайних точек с использованием только тех граней их ячеек диаграммы Вороного, которые пересекаются отрезком между точками, эту грань породившими, решает задачу ЛП для оставшихся после двух предыдущих предобработок точек множества Sunknown (возможно уменьшившегося после предыдущей предобработки)- Используются ограничения, параллельные таким граням ячейки диаграммы Вороного точки, что каждая из этих граней пересекается отрезком между точками, эту грань породившими. Число элементов множества Sunknown, а следовательно и S* может уменьшаться.

И наконец, для точек Sunknown, оставшихся после удаления заведомо не крайних, кроме заведомо крайних точек Svertex, решается задача ЛП с использованием ограничений, порожденных оставшимися точками множества S.

В § 1.4 описываются дополнительные построения.

Координаты точек преобразуется так, чтобы для каждой оси координат минимальная координата точек исходного множества S по этой оси координат была равна некой заданной константе _ (DISPLASEMENT + 0.5) . Это делается потому, что для задачи ~ ЛП предполагается наличие ограничений: X] > 0,...,xd > 0.

Вводится система из 2d дополнительных ограничений: х, > 0.5

x<j > 0.5

X! < 2*DISPLASEMENT + (х^-х™11) + 0.5

Xfj < 2*DISPLASEMENT + (x™x-x™n) + 0.5 ,

где (х^-х!™) - расстояние между наибольшей и наименьшей координатами по каждой оси для точек множества

В* § 1.5 описана предобработка, предназначеная для нахождения некоторого подмножества 5уеЛех множества крайних точек. С ростом размерности пространства персятиссть того, что большее число точек множества Б* будут крайними увеличивается и если точек исходного множества не очень много, то возможна ситуации, когда подавляющее большинство точек исходного множества (а возможно и все) будут крайними. Время решения задачи ЛП возрастает с ростом размерности пространства, поэтому возрастает и время работы алгоритма. Поэтому применяется предобработка, которая позволяет быстро найти некоторое подмножество крайних точек, чтобы в дальнейшем не использовать задачу ЛП для определения крайности некоторого подмножества 8УСПех множества крайних точек. Все найденные крайние точки запоминаются (множество 5уепех) и далее не анализируется. Кроме того, внутренние точки для выпуклой оболочки, построенной для множества 8УеЛех, ищутся с помощью задачи ЛП для меньшего числа ограничений.

В § 1.6. описывается, как получается первая выборка ограничений для задачи Кларксона и обосновывается выбор целевой функции из числа этих ограничений.

В § 1.7 описывается, на каких критериях основываются дальнейшие выборки в методе Кларксона.

§ 1.8 посвящен решению задачи ЛП методом Кларксона с учетом дополнительных 2д ограничений, предложен метод, позволяюший уменьшить число итераций или размер выборки на некоторой итерации путем отбрасывания ограничений.

В § 1.9 рассмотривается алгоритм для удаления заведомо не крайних точек с использованием тех граней их ячеек диаграммы Вороного, которые пересекаются отрезком между точками, их породившими. Критерий, иcпoльзveмый в этом алгоритме является необходимым, но не достаточным условием того, что течка принадлежит множеству крайних точек. Для точек, которые не били определены как крайние и не были отброшены как внутренние, производится предобработка с использованием

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

§ 1.10 посвящен анализу полученных результатов.

Вторая глава посвящена описанию устойчивого алгоритма для построения и динамического преобразования диаграммы Вороного множества точек и для определения различных характеристик ячеек диаграммы Вороного (или возможно их частей, лежащих внутри ограничения) внутри ограничения, являющимся простым многоугольником. Обрабатываемые этим алгоритмом точки и ограничение могут содержаться только внутри рабочей области, представляющей собой прямоугольник. К числу анализируемых характеристик с учетом ограничения относятся:

1) площадь ячейки диаграммы Вороного;

2) площади частей тех ячеек диаграммы Вороного, которые были бы отсечены от них при добавлении в диаграмму Вороного какой-либо точки, то есть при псевдодобавлении точки;

3) центр масс ячейки диаграммы Вороного.

Программа, реализующая этот алгоритм работает в режиме реального времени.

В § 2Л обсуждается выбранный подход для решения поставленной задачи.

Поведенные исследования показам, что алгоритм для работы с ячейками диаграммы Вороного, представленными только своими частями, находящимися внутри ограничения, весьма сложен и- что самое неприемлимое - требует значительных затрат памяти. Поэтому был выбран подход, когда ячейки диаграммы Вороного хранятся в обычном виде, который не учитывает наличие ограничения. При вычислении той или иной характеристики ячейки диаграммы Вороного каждый раз определяется пересечение этой ячейки с многоугольником ограничения и получаемый при этом простой многоугольник (возможно пересечение будет являться несколькими простыми многоугольниками) представляется в

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

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

§ 2.2 посвящен модели представления данных и дополнительным построениям.

Точки, для которых строятся ячейки диаграммы Бортного, не могут находится вне прямоугольной области, называемой рабочей областью. х$п > Х™х , У$п> являются мини-

мальными и максимальными координатами (по х и по у соответственно) рабочей области, т. е. любая точка (х,у), образующая ячейку диаграммы Вороного, должна удовлетворять неравенствам:

ХТ <х< хТ>

УТ <У< УТ-

Рабочая область разбита на квадратики со стороной а^ц, где каждый квадратик хранит информацию о точках и ребрах ограничения, в него попавших.

Величина асец вычисляется по формуле: .

асе!1 = ((Х&ах -ХТ) *(УТ - ¥$")/ , где

1^ро;т - максимальное число точек, для которых строится диаграмма Вороного.

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

Идея дополнительных построений заключается в том, что вводятся четыре дополнительные точки, в результате чего вершины диаграммы Вороного исходного множества точек не могут лежать вне некого прямоугольника, содержащего внутри

себя рабочую область, который называется расширенным и координаты которого лежат в пределах:

хтт<х<хтах5

у«т < у < утах.

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

Четыре дополнительные точки выбираются на лучах, являющихся биссектрисами углов, смежных с углами прямоугольника при каждой вершине.

Назовем расстоянием Д:

Д = мах ((ХТ-ХТШТ-ХТ)'(УТ-УТЫУТ-УТ))-

Пусть Л] - длина диагонали прямоугольника, задающего рабочую область.

Пусть Д2 - расстояние от каждой дополнительной точки до начала луча, на котором она расположена. Это расстояние одинаково для всех четырех точек.

Теорема. Расстояние Д будет минимальным, если для е>0:

Д2 = Д] + е, е-* 0.

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

Основным ' шагом построения триангуляции , являгтся нахождение для двух известных точек третьей, обладающей тем свойством, что внутри окружности, проведенной-через эти три. —-точки, не будет других точек исходного множества.

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

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

Имеющееся ограничение требуется представить в таком виде, чтобы иметь возможность определять те ребра ограничения, которые попали в прямоугольник, состоящий из квадратиков сети и содержащий в себе исследуемый объект. Такой подход наиболее приемлем, так как перебирать все ребра ограничения для работы с локализованным объектом неэффективно.

Для реализации выбранного подхода требуется знать, какие ребра ограничения содержатся в каждом квадратике сети. В этом случае для каждого квадратика сети должна иметься информация о:

- количестве пересекающих квадратик ребер;

- номерах пересекающих квадратик ребер.

Очевидно, что при таком подходе все квадратики сети будут делиться на те, которые пересекаются ребрами и на те, которые не пересекаются. Квадратики сети, которые не пересекаются ребрами, в свою очередь, делятся на расположенные внутри ограничения и вне ограничения.

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

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

Удобным для работы объектом является композитный контур, представляющий собой простой многоугольник, ребрами которого являются части ребер выпуклого многоугольника и ограничения. Композитный контур описывает одну (возможно из нескольких) односвязанных областей, полученных при пересечениии выпуклого многоугольника (ячейки диаграммы Вороного) с ограничением. Композитный контур представляется в' виде замкнутого односвязанного списка.

Такое представление обеспечивает инкапсуляцию данных и позволяет функциям, вычисляющим различные характеристики ячеек диаграммы Вороного при наличии ограничения, работать только с одним объектом - композитным контуром.

В § 2.5 приводится алгоритм вычисления площади композитного контура.

Благодаря предыдущим построениям композитный контур является ориентированной фигурой, поэтому его площадь вычисляется по известной формуле:

8=1/2Ч(хгх2)*(у,+у2) + (х2-х3)*(у2+у3) + - +(хп-х,)*(Уп+У1)].

Если при нахождении площади ячейки приходится работать с-несколькими композитными контурами, то площади этих композитных контуров суммируются.

В § 2.6 приводится алгоритм вычисления центра масс композитного контура.

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

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

В § 2.8 приводится алгоритм удаледия точки.

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

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

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

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

обстоятельствами: во-первых, только при использовании динамической памяти возможно экономное и достаточно эффективное распределение ограниченных ресурсов памяти ЭВМ и, во-вторых, поведение динамических объектов полностью определяется программистом.

В § 3.1 описана программная реализация Главы 1. Сначала описываются функции, служащие для преобразования исходных данных к виду, удобному для дальнейшего использования. Это требуется для того, чтобы генерируемые впоследствии для задачи ЛП ограничения были представлены в нужном виде.

Важное место занимает описание функции, предназначенной для нахождения некоторого подмножества крайних точек. Очевидно, что точки найденного подмножества далее не исследуются, следовательно для каждой из них че генерируется и не решается задача ЛП.

Особое внимание уделяется функциям, генерирующим ограничения. Особенность решаемой задачи заключается в том, что ограничения задачи ЛП были получены малым смещением из своего первоначального положения, когда соответствующие им гиперплоскости являлись пучком гиперплоскостей. Поэтому генерация ограничений для первой выборки в методе Кларксона имеет особое значение. Эффективность алгоритма повышается, если задачу ЛП решать, используя в первоначальных выборках ограничения, параллельные тем граням ячейки диаграммы Вороного, которые пересекаются отрезком между рассматриваемой точкой и точками, эти грани породившими. Функция, генерирующая целевую функцию для задачи ЛП, выбирает ее параллельной определенному ограничению.

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

Задача ЛП для генерируемых в методе Кларксона выборок из некоторого числа ограничений решается при помощи улучшенного симплекс-метода Данцига. . Причем решается двойственная задача ЛП. При таком подходе достигается большая экономия памяти и времени, так как вычисления производятся в матрице размера <1хс1 (с1 - размерность •пространства), а изначально предполагается, что" размерность пространства значительно меньше числа- ограничений.

В § 3.2 описана программная реализация Главы 2. Сначала описываются функции, служащие для создания базы данных, элементами которой являются квадратики покрывающей рабочую область сети. Каждый квадратик содержит информацию о точках и ребрах ограничения в него попавших.

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

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

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

- площадь;

- ценр масс.

Реализована функция триангуляции простого многоугольника, что требуется при вычислении центра масс.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработан алгоритм, позволяющий решать задачу нахождения крайних точек заданного множества S в d-мерном евклидовом пространстве Ed без нахождения граней выпуклой оболочки множества точек S.

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

3. Разработан основанный на введении дополнительных построений алгоритм получения диаграммы Вороного множества точек на плоскости. Особенностью этого алгоритма является то, что границы ячеек диаграммы Вороного исходного множества

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

4. Осуществлена программная реализация разработанных алгоритмов. Проведенное тестирование подтвердило эффективность используемых подходов для решения подобного класса задач.

Ниже приводятся некоторые результаты тестов, проведенных на IBM PC 486/66Mz.

Множество крайних * точек для каждого • множества, состоящего из 1000 точек в пространствах размерности 7-15 можно найти за время не более 5 минут.

Построить диаграмму Вороного при наличии прямоугольного ограничения можно за время; 1000 точек - 1.56 сек,-2000 -3.49 сек.

По теме диссертации опубликованы следующие работы:

•1. Мартишин С.А. Параллельные алгоритмы построения выпуклой оболочки // Вопросы кибернетики. Средства моделирования и разработка прикладного программного обеспечения для суперЭВМ, Москва 1992.

2. НТО по НИР "Проведение фундаментальных и прикладных исследований, связанных с моделированием управляемых объектов, совершенствованием структуры .' и принципов построения современных тренажеров М.:МГИЭМ, 1993, N гос. регистрации 01920019470.

3. Мартишин С.А. Алгоритм нахождения крайних точек множества в Э-мерном евклидовом пространстве с использованием линейного программирования. // Вопросы

.кибернетики. Приложения системного программирования, Москва,' 1995.

4. Мартишин С.А. Динамический алгоритм вычисления некоторых характеристик ячеек диаграммы Вороного на плоскости с ограничениями. // Вопросы кибернетики. Приложения системного программирования, Москва, 1996 (в печати).

Подписано в печать 15 апреля 1996 г. Закай № 47/174 Тираж 100 экз. П.л. 1.2

Ротапринт НПО имЛавочкина