Введение к работе
Актуальность темы. В течение последних двадцати пяти лет анализ и построение вычислительных алгоритмов остаются одной из самых продуктивных областей информатики.
Важной составной частью вычислительной математики является вычислительная геометрия.
Предметом вычислительной геометрии являются разработка и исследование вычислительных моделей, методов и алгоритмов решения разнообразных геометрических задач при помощи ЭВМ.
В настоящее время в связи с успешным развитием вычислительной техники и прежде всего с широким распространением персональных компьютеров вычислительная геометрия, как научное направление, интенсивно развивается. Интенсивное развитие вычислительной геометрии обусловлено широким кругом ее применения. Это экономика, геология, география, физика твердого тела, статистика, математическая экология, робототехника, распознавание образов, обработка изображений, проектирование СБИС, базы данных, машинная графика, раскрой и компановка материала, астрономия, решение экстремальных задач и многое другое.
На современном этапе наряду с исследованиями в двумерном и трехмерном евклидовых пространствах, являющихся традиционными объектами вычислительной геометрии, все больше внимания уделяется многомерным евклидовым пространствам. Это обусловлено усложнением методов теоретических исследований, основанных на геометрических' интерпретациях, что приводит к необходимости введения многомерных моделей и обработки многомерных данных в различных областях науки її техники.
Особый интерес представляет решение больших задач вычислительной геометрии, характеризующихся или большим объемом обрабатываемых данных или сложной комбинаторной структурой или комплексом этих свойств. До недавнего времени из-за отсутствия широкодоступной быстродействующей вычислительной техники решение этих задач представлялось невозможным или требовало больших затрат машинного нремени, что
делало затруднительным их широкое использование, и что естественно, не способствовало разработке алгоритмов для подобного класса задач. Поэтому диссертационная работа посвящена решению больших задач вычислительной геометрии.
Целью работы является решение двух больших задач вычислительной геометрии.
Первая задача - задача1 нахождения крайних точек для
множества точек S в d-мерном евклидовом'пространстве Ed. Эта
задача является большой, потому что в пространствах больших
размерностей выпуклая оболочка множества точек имеет
сложную комбинаторную структуру. Следует заметить, что число
граней политопа с N вершинами определяется величиной
0(NLd/2j). '
Вторая задача - задача построения диаграммы Вороного на плоскости с ограничением, заданным простым многоугольником, для ячеек которой вычисляются различные характеристики. Эта задача является большой, так как приходится работать с большим размером входных данных, причем решение этой задачи должно выполняться в режиме реального времени.
Научная новизна работы состоит в следующем.
Разработан алгоритм, позволяющий решать задачу —. нахождения крайних точек заданного множества точек S р d-мерном евклидовом пространстве Ed без нахождения граней выпуклой оболочки множества точек S. Анализ каждой точки осуществляется путем решения \задачи линейного программирования (задачи ЛП). Алгоритм лЪрк&-распараллеливается, так как для определения того, является ли какая-либо точка крайней достаточно знать только координаты других точек множества.
- Разработан основанный на введении дополнительных построений алгоритм получения диаграммы Вороного множества точек на плоскости. Особенностью этого алгоритма является то, что границы ячеек диаграммы Вороного исходного множества точек представляют собой выпуклые многоугольники, вершины которых содержатся внутри прямоугольника с наперед известным конечным размером.
Практическая ценность. С помощью разработанного алгоритма нахождения крайігах точек для множества точек S в пространстве Ed может быть осуществлена локализация точки, то есть определено, внутри или вне выпуклой оболочки множества S находится точка, а также решены ряд вероятностных и
СТаТИСТйЧсСКИХ ЗйДаЧ. ivpOMC ТОГО, ПрСДБарКТСЛЬНСС КЗХОЖДСНИС
крайних точек упрощает нахождение выпуклой оболочки.
Предложенный алгоритм построения диаграммы Вороного на плоскости с ограничением используется для решения задач, применяемых для геологического моделирования свойств залежей нефти и газа и оптимизации разведки залежей:
интерполяция геолого-геофизических признаков;
построение карт;
моделирование поверхностей;
оптимизация размещения разведочных скважин.
Апробация работы. Основные результаты работы неоднократно докладывались на семинарах в Институте проблем кибернетики РАН (1988 - 1993гг.) и в Институте системного программирования РАН (1994 - 1996гт.).
Высокая. практическая значимость решаемых задач подтверждена актами о внедрении:
1) математического и программного обеспечения в рамках
темы "Решение задач нахождения оптимальных стационарных
стратегий в марковских процессах принятия решений"
(МГИЭМ, кафедра "Исследование операций", 2 июня 1994г.);
2) математического и программного обеспечения
(ВНИГНИ, отдел 4, сектор 4.1, 29 марта 1995г.).
Публикации. Представляемые к зашите результаты опубликованы в работах [1-4].
Объем и структура диссертации. Диссертация состоит из введения, трех глав и заключения. Ее общий объем 84 страницы, в,том числе 4 рисунка, 2 таблицы и список литературы из 69 наименований.
