Минимальные циклы в заданных классах гомологий

Лаптева, Анастасия Владимировна

Минимальные циклы в заданных классах гомологий тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

Лаптева, Анастасия Владимировна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Нижний Новгород МЕСТО ЗАЩИТЫ

2006 ГОД ЗАЩИТЫ

01.01.04 КОД ВАК РФ

Диссертация по математике на тему «Минимальные циклы в заданных классах гомологий»

Автореферат диссертации на тему "Минимальные циклы в заданных классах гомологий"

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

ии^и54021

Лаптева Анастасия Владимировна

МИНИМАЛЬНЫЕ ЦИКЛЫ В ЗАДАННЫХ КЛАССАХ ГОМОЛОГИЙ

01.01.04 - геометрия и топология

Автореферат

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

Казань - 2007

003054021

Работа выполнена на кафедре геометрии и высшей алгебры механико-математического факультета Нижегородского государственного университета имени Н.И. Лобачевского.

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

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

доктор физико-математических наук, профессор Шурыгин Вадим Васильевич

Ведущая организация -Челябинский государственный университет

Защита состоится 29 марта 2007 года в 14 часов 30 минут на заседании диссертационного совета Д 212.081.10 при Казанском государственном университете по адресу: 420008, г. Казань, ул. Кремлевская, 18, корп. 2, ауд. 217.

С диссертацией можно ознакомиться в Научной библиотеке Казанского государственного университета. Автореферат разослан 15 февраля 2007 г.

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

доцент

М.А. Малахальцев

Общая характеристика работы

Актуальность темы. В последние два десятилетия сформировалась и активно развивается вычислительная топология, в которой соединяются два различных, хотя и связанных друг с другом направления. Первое - это использование компьютерных методов при решении тех или иных проблем самой топологии, например, классификации компактных трехмерных многообразий в работах C.B. Матвеева 1>2. Второе направление можно обозначить как приложения топологии к задачам, связанным с компьютерным моделированием и компьютерной графикой.

Настоящая работа в большей степени относится ко второму из указанных направлений.

Существует много работ, в которых предлагаются различные подходы к вычислению топологических характеристик и элементов полиэдров. Можно отметить классический алгоритм для вычисления групп гомологий и их базисов произвольного симплициального комплекса, основанный на приведении матриц инциденций к нормальной диагональной форме. В работах J. Chao и J. Nakayama3, J. Friedman4 предлагались различные его Модификации.

Для поверхностей известен ряд методов, основанных на использовании представления ее в виде канонического многоугольника. Так, в работах G. Vegter и С. К. Yap5, F. Lazarus и др.6 предложен алгоритм поиска базиса одномерной группы гомологии замкнутой поверхности. С помощью канонического представления решаются задача построения базиса фундаментальной группы поверхности из пе-

1 Матвеев, С. В. Алгоритмическая классификация 3-многообразий Проблемы и результаты / С. В Матвеев // Труды Математического института имени В.А. Стеклова. - 1999 - Т 225 - С. 264-275

2Матвеев, С В. Табулирование трехмерных многообразий / С. В. Матвеев // Успехи математических наук - 2005. - Т. 60. N 4. - С. 97-122.

3Chao, J Cubical singular simplex model for 3D objects and fast computation oí homology groups / J. Chao, J Nakayama // Proc IEEE. - 1996. - P. 190-194.

4fViedman, J Computing Betti numbers via combinatorial Laplacians / J Friedman j j Proc 28th ACM Sympos Theory Comput. - 1996 - P. 386-391

5Vegter, G Computational Complexity of Combinatorial Surfaces / G. Vegter, С К. Yap // Proceedings of the 6th Annual Symposium on Computational Geometry. - 1990. - P. 93-111.

^Lazarus, F Computing a Canonical Polygonal Schema of an Orientable TViangulated Surface / F. Lazarus, M. Pocchiola, G. Vegter, A Verroust // Proc. 17th Annu. ACM Sympos Comput. Geom.-2001 -P 80-89

тель минимальной длины (Е. Colin de Verdiere, F. Lazarus7) и задача определения гомотопности двух заданных кривых (Т.К. Dey, S. Guha 8'9).

В работах H. Edelsbrunner и соавторов 10'и разработан алгоритм вычисления групп гомологий трехмерного симплициального комплекса, основанный на построении триангуляции Делоне. Другой метод решения аналогичной задачи предложен в серии работ Т.К. Dey, S. Guha 12-13-14.

Нематричным методам поиска циклов, порождающих базисы групп гомологий для двумерных многообразий, посвящены работы Е.И. Яковлева и его учеников 15,16'17.

В работе X. Gu, S. J. Gortier и H. Hoppe18 с помощью процедуры, аналогичной коллапсированию, построен алгоритм нахождения графа разрезания, однако авторы не ставят задачу построения базисных циклов, а лишь находят граф, их содержащий.

Большая серия работ связана с применениями в вычислитель-

7Colm de Verdiere, Е Optimal System of Loops on an Orientable Surface / E Colin de Verdiere, F Lazarus // Proceedings of the 43rd Annual IEEE Symposium of Foundations of Computer Science - 2002 - P 627-636

®Dey, Т. К Optimal algorithms for curves on surfaces / T K. Dey, S. Guha // Proc 35th IEEE Ann Sympos. Found. Comput. Sci. - 1995 - P. 266-274.

9Dey, Т. K. Transforming Curves on Surfaces / Т. K. Dey, S. Guha // J. Comput. Sys. Sci. -1999 Vol 58 - P. 297-325

10Delfinado, С An incremental algorithm for betti numbers of simplicial complexes on the 3-sphere / C. Delfinado, H Edelsbrunner // Comput Aided Geom. Design. - 1995 - Vol 12 - P 771-784

^Edelsbrunner, H. Topological Persistence and Simplification / H. Edelsbrunner, D. Letscher, A Zomorodian // Disc. Comput. Geom 28. - 2002. - P. 511-533.

12Dey, Т. К Computational topology / T. K. Dey, H. Edelsbrunner, S Guha // Advances in Discrete and Computational Geometry. - Providence, 1998 - P. 109-143.

13Dey, Т. К Algorithms for Manifolds and Simplicial Complexes in Euclidean 3-Space / Т. К Dey, S Guha // Proc 28th ACM Sympog. Theory Comput. - 1996 - P 398-407.

14Dey, T. K. Computing Homology Groups of Simplicial Complexes in R3 / T K. Dey, S Guha // Proceedings ot 28th Symposium of Theory of Computing - 1996 - P. 397-407.

г5Зинченко, В. Ю. Новый метод построения базисных циклов групп гомологий полиэдров / В. Ю Зинченко // Труды Математического центра имени Н.И. Лобачевского. - 2003. - Т. 21. -С 118-120

16 Яковлев, Е. И. Быстрые алгоритмы вычисления групп гомологий и их базисов / Е. И Яковлев, П А Гордиенко / / Материалы VII Международного семинара "Дискретная математика и ее приложения". - 2001 - С. 284 - 287.

17Яковлев, Е. И. Алгоритмы для вычисления базисных циклов одномерной группы относительных гомологий / Е. И. Яковлев, О. В. Логинов // Вестник ННГУ. Серия Математика -2003 - Вып. 1. - С 132 - 142

18Gu, X. Geometry Images / X Gu, S. J. Gortler, H. Hoppe // Proc. SIGGRAPH'02. - New York, 2002. - P 355 - 361.

ных алгоритмах дискретного аналога теории Морса. В частности, на основе подобных методов в работах I. Guskov и Z. Wood19, Z. Wood и др.20 предлагается один из способов устранения топологического шума, то есть топологических дефектов компьютерных моделей.

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

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

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

Целью работы является разработка методов решения следующих задач:

1) индексация ребер триангулированного замкнутого п-мерного многообразия Р относительно заданного (п — 1)-мерного цикла Y €

2) построение симплициального регулярного накрытия р : Pj —>■ Р с группой накрывающих преобразований G = Hi(P)\

3) поиск цепей с £ Ci(P), минимизирующих весовую функцию L : Ci(P) —>• R на заданном подмножестве группы Ci(P);

Методы исследования. Использованы методы алгебраической и кусочно-линейной топологии, теории графов.

Результаты, выносимые на защиту.

1. Предложен способ индексации одномерных симплексов триангулированного замкнутого многообразия Р относительно заданного цикла z € Zn-i(P). С его помощью строится гомоморфизм Jz : С\(Р) —у Z2, позволяющий вычислить индекс пересечения г с любым одномерным циклом полиэдра Р, а также индексная вектор-функция J : Ci(P) —> относительно базиса [г"-1],..., [-г"-1] группы гомологий #n_i(P).

19Guskov, I Topological Noise Removal / I. Guskov, Z. Wood // Graph Interf. - 2001. - P 19-26.

20Wood, Z Removing Excess Topology From Isosurfaces / Z. Wood, H. Hoppe, M Desbrun, P Schroder // ACM Transactions on Graphics - 2004. - Vol 23, No 2. - P 190 - 208

2. Построена симплициальная схема полиэдра pJ, симплициально и регулярно накрывающего многообразие Р с группой накрывающих преобразований С = Н\(Р).

3. Разработаны методы минимизации весовой функции Ь : С\{Р) —> Ж на следующих подмножествах группы С\(Р) замкнутого многообразия Р:

• на множестве путей, соединяющих фиксированные вершины и имеющих заданный индекс;

• на множестве одномерных цепей, соединяющих вершину и многообразия Р с некоторым подполиздром ф С Р и образующих класс относительных гомологий [я] € Н\{Р, {и} и

• на произвольном ненулевом гомологическом классе [х] € Н\(Р).

4. Указан способ построения минимальных циклов, порождающих базис группы Н\{Р), дуальный заданному базису группы Нп-\{Р).

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

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

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

Апробация. Описанные результаты работы были обнародованы на международной научной конференции "Актуальные проблемы математики и механики"(Казань, 26 сентября - 1 октября 2004 г.); на всероссийских молодежных научных школах-конференциях "Лобачевские чтения"(Казань, 2005г., 2006г.); на международных летних школах-семинарах по современным проблемам теоретической и математической физики "Петровские чтения"(Казань, 2005г., 2006г.); на III международной конференции по прикладной математике (Пловдив, Болгария, 12-18 августа 2006 г.); на региональной научной конференции "Современные вопросы геометрии и механики деформируемого твердого тела"(Чебоксары, 19-20 октября 2006г.); на научных

семинарах по геометрии и топологии кафедры геометрии и высшей алгебры ННГУ (рук. доц. Н.И. Жукова и проф. Е.И. Яковлев, 2005г., 2006г.); на научном семинаре кафедры компьютерной топологии и алгебры Челябинского госуниверситета (рук. член-корр. РАН С В. Матвеев, 2006г.).

Публикации и вклад автора. Результаты диссертации опубликованы в 11 работах, список которых приведен в конце автореферата. В совместных статьях [1], [2], [6] и [9] научному руководителю Е.И. Яковлеву принадлежат постановка задачи и общее руководство работой. Все теоремы и их доказательства получены автором диссертации.

Структура и объем работы. Диссертация состоит из введения, четырех глав, разбитых на разделы, заключения, списка литературы и включает в себя 7 рисунков. Объем диссертации составляет 102 страницы. Список литературы состоит из 67 наименований.

Краткое содержание работы.

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

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

Глава 2 посвящена построению симплициальных регулярных накрытий р : PJ Р с заданной группой автоморфизмов.

В §2.1 разработан способ индексации ребер замкнутого многообразия Р относительно заданного (п — 1)-мерного простого цикла 2. Это означает построение индексной функции Jz : К1{Р) —> 112, где К1 (Р) - набор одномерных симплексов (ребер) полиэдра Р.

Конкретной реализацией метода является Алгоритм 2.1.

Теорема 2.1. Если Р - замкнутое п-мерное многообразие, г -простой (п — 1)-мерный цикл, х — + • ■ • + а/ £ 2\(Р) и «7г(ж) = Е!=1 ! где Л - функция, построенная с помощью алгоритма 2.1, то 7г(ж) = 1пс1([х], [г]).

В §2.2 мы определяем индексную вектор-функцию относительно

заданного базиса группы гомологий Я„_1(Р) и исследуем ее свойства.

Определение 2.1. Пусть [г"-1],..., [г"-1] - базис группы гомологий Я„_!(Р). Гомоморфизм 3 : С^Р) ->• 1Г2, 3 = (31,...,3Г), будем называть индексной вектор-функцией относительно базиса [г"-1],..., [г"-1], если для произвольного цикла у £ Z^(P) и каждого к е {1,..., г} имеет место равенство ^(у) = 1пс1([у], [г""1]). При этом для любой цепи х € С\(Р) элемент 3(х) £ далее будет называться ее индексом.

Согласно теореме 2.1, индексная вектор-функция 3 : С\(Р) —> может быть вычислена с помощью алгоритма 2.1.

Предложение 2.1. Если 3 : С\ (Р) —> - индексная вектор-функция относительно базиса [г"-1],..., [г"-1] группы Я„_1(Р), ж, у е С\{Р) и дх — ду, то 3(х) = 7(у) тогда и только тогда, когда х ~ у.

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

В §2.4 строятся симплициальные регулярные накрытия р : Р Р с группой накрывающих преобразований С =

Пусть 5 = (V, К) - симплициальная схема полиэдра Р, а 3 : С^Р) —172 - эпимоморфизм, ядро которого содержит группу границ ВДР). Построим схему 5 = (У, К) следующим образом.

Положим V = V х б, где С? = Пусть г>о, щ,..., ут е V, где г), = (у,, д,) для всех г = 0,1,..., т. Будем считать, что {г)0, щ,..., г)т} € К, если выполняются следующие условия:

• {г>о,иъ...,ит} € К\

• 9а+91 — «7([г701^г]) Для любых г = 1,..., т.

Определим отображение р° : V -4 V и левое действие А0 : С х У — V группы (7 на У, полагая

для всех (г>, д) к д' Е С.

Символом Р/ обозначим какую-либо реализацию схемы 5 — (V, К). При этом множество вершин полиэдра Р/ отождествим с ТЛ

Теорема 2.2. Для отображения р° : V —► V" существует продолжение р : Р] —> Р, являющееся симплициалъным регулярным накрытием с группой накрывающих преобразований О = Щ. Если Р

- замкнутое многообразие, а 3 - индексная вектор-функция относительно некоторого базиса группы Нп~\{Р), то (7 = Н^Р).

В §2.5 сформулированы существенные для дальнейших исследований свойства построенного регулярного накрытия р : Рз —> Р.

Предложение 2.2. Пусть х = [^х] + [г)^] Н-----Ь- путь

в полиэдре Р и до £ С = Щ. Тогда единственный путь х полиэдра Р./, начинающийся в вершине до = (г>0, до) и накрывающий путь х, определяется формулами

V, = (У„д0 + г = 1,...,в,

где х, - [г/о^г] + [и^г] Н-----Ь [и,-IV,], и

х = [г)0г>1] + [€гг>2] +----Ь [^.-1^]-

Предложение 2.3. Пусть х = [«0^1] + [иг^г] + • ■ • + К-г^] и у = [иои1] + [«1«г] Н-----Ь - пути полиэдра Р, идущие из вер-

шины = ио в вершину = щ, х = [¿о^г] + [г>1г>2] + • • • + и

у — [¿0^1] + [г^йг] Н-----1- [й(_хй(] - пути в Р/, накрывающие пути х

и у соответственно и имеющие общее начало йо — щ. Тогда г)3 = щ в том и только том случае, если = ./(у). В случае когда Р

- замкнутое многообразие, а 3 - индексная вектор-функция относительно некоторого базиса группы Нп-\(Р), последнее равносильно гомологичности цепей х и у.

В Главе 3 разработаны и обоснованы методы построения цепей с е С\(Р), минимизирующих неотрицательную весовую функцию Ь : Сг(Р) —>■ К на заданном подмножестве группы С\{Р).

В §3.1 рассматриваются весовые функции на группах 1-цепей полиэдра Р и накрывающего его полиэдра Р].

В §3.2 получены Алгоритм 3.1 и его обоснование - теорема 3.1, посвященные вспомогательной задаче о поиске минимального пути с заданными концами и формальным индексом в произвольном полиэдре Р.

Пусть далее Р - триангулированное замкнутое многообразие размерности п, 1: С\(Р) —> 25 - индексная вектор-функция относительно некоторого базиса группы гомологий #„_1(Р), а Ь : С\(Р) —> М -весовая функция. Оставшиеся в главе 3 §§3.2-3.5 содержат методы решения следующих задач.

1. Заданы вершины 111,112 £ У(Р) и вектор г 6 С — Ъ\. Ищется цепь ^ 6 С\ (Р), обладающая свойствами:

• дг = {«1,112};

• = г;

• Ь(г) < Ь(у) для всех цепей у £ С\{Р), удовлетворяющих условиям J(y) = г и ду — {«1,^2}.

2. Пусть <5 С Р - подполиэдр, 141 - вершина полиэдра Р, а

(Р, г^иф) и Н1(Р,и1и<3) - группы относительных циклов и гомологий с коэффициентами из поля Для цепи с 6 С\(Р) договоримся полагать с — с + С^щ и

Задана цепь х £ Сг(Р) и дх = {«1, и2}, где и2 - некоторая вершина подполиэдра <3. Строится цепь г 6 С^Р), удовлетворяющая условиям:

• их € дг С иг и <?;

. [Щ^^вН^щиС})-,

• Ь{г) < Ь(у) для всех у £ [х] и у £ у.

3. Заданы простые циклы г"-1,..., г"-1, порождающие базис группы гомологий #П_3(Р), и одномерный цикл х £ 2г(Р), [х] ф 0. Находится одномерный цикл обладающий свойствами:

• 2 ~ Х\

• Цг) = гтпЬ{у).

у е[х]

4. Пусть [г"-1],..., [г"-1] - базис группы Я„_1(Р), относительно которого построена индексная вектор-функция 3 : С\(Р) —> 1%. Решается задача построения циклов г\,.г]., гомологические классы

которых образуют базис группы гомологий Нх(Р), дуальный базису [г"-1],..., [г""1], а вес каждого цикла к = 1,..., г, минимален среди весов всех циклов, ему гомологичных.

Основная идея предлагаемых методов решения сформулированных задач состоит в их редукции к задачам поиска путей в одномерном остове накрывающего полиэдра PJ, минимизирующих весовую функцию Ь : С\(Р^ ->Ки удовлетворяющих подходящим краевым условиям. Алгоритмы 3.2 - 3.5 являются их реализациями, а теоремы 3.2 - 3.5 - обоснованиями.

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

В §4.1 разработан метод построения простых циклов, порождающих базис группы гомологий Н\{Р) двумерного многообразия Р без применения матриц инциденций. Алгоритм 4.1 представляет собой реализацию этого метода, а теорема 4.2 - обоснование.

Пусть Р - двумерное замкнутое ориентируемое многообразие, а Ь : С\{Р) —> Е - весовая функция. В §4.2 решается задача нахождения циклов гомологические классы которых образуют канонический базис группы гомологий Н\(Р), а вес каждого цикла

к = 1,...,г, минимален среди всех циклов, ему гомологичных. Метод решения этой задачи реализован в алгоритме 4.2, обоснование содержится в теореме 4.2.

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

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

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

Пусть Р - триангулированное замкнутое и ориентируемое 2-

многообразие рода т и Т(Р) - список его треугольников. Выделением ручки мы называем составление такого списка T(R) С Т(Р), что объединение R всех его элементов гомеоморфно ограниченному цилиндру, а объединение симплексов из дополнения Т(Р) \ T(R) представляет собой поверхность Р' рода m — 1с двумя компонентами края. По списку T(R) можно определить отношение размеров ручки R к соответствующим размерам всей поверхности Р, что в ряде случаев позволяет оценить правильность отнесения R к топологическому шуму. При этом исправление модели осуществляется удалением T(R) из общего списка треугольников Т(Р) и заклеиванием получающихся дыр.

Предлагаемая схема выделения ручек поверхности Р состоит в следующем:

1. С помощью алгоритма 4.1 найдем циклы j/i,..., yr, г = 2т = rank Hi(P), гомологические классы которых образуют базис группы Н,{Р).

2. Воспользуемся алгоритмом 2.1 и вычислим индексную вектор-функцию J0 : Ci(P) -> Ъ\ относительно базиса [j/i],..., [уг] группы Я,(Р).

3. Применяя алгоритм 4.2, построим циклы Zi,... ,zr, каждый из которых имеет минимальный вес в своем классе гомологий, а эти классы образуют канонический базис группы Hi(P). При этом мы получим также индексную вектор-функцию J : С\{Р) —> Щ относительно базиса [zi],..., [zr].

4. Для каждой пары циклов x^fc-i и z2k, к — 1,... , т, выполним следующие шаги:

4.1. Выберем основной цикл х G {z2k-i,z2k} и дополнительный цикл у € {z2k-i, Z2k}, У ф х (например, по длине).

4.2. Для каждой вершины vu i = 1,... , основного цикла х в одномерном остове накрывающего полиэдра Pj найдем кратчайший путь у„ идущий из вершины (г>„0) в вершину J(y)), и положим Уг=Р{У,)-

4.3. Начиная с треугольника, инцидентного ребру (г+1 вычисляется по модулю Пк), построим список Т, треугольников, расположенных между циклами у, и yi+i- Для объединения U% симплексов из Tt вычислим группу H\(UX).

4.4. Построим максимальное по включению сильно связное объ-

единение Rk областей (/;, для которых rank^i(i7i) ^ 1.

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

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

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

1. Лаптева, А. В. Методы поиска кратчайших 1-циклов в заданном классе гомологий / А. В. Лаптева, Е. И. Яковлев // Труды матем. центра им. Н.И. Лобачевского. - 2004. - Т. 25. - С. 159-160.

2. Лаптева, А. В. Алгоритмы для поиска минимальных одномерных циклов / А. В. Лаптева, Е. И. Яковлев // Вестник ННГУ. Серия Математика. - 2005. - Вып. 1(3). - С. 76-87.

3. Лаптева, А. В. Поиск минимального пути в заданном классе относительных гомологий / А. В. Лаптева // Труды матем. центра им. Н.И. Лобачевского. - 2005. - Т. 31. - С. 88-89.

4. Лаптева, А. В. Метод устранения топологического шума в компьютерных моделях ЗО-объектов / А. В. Лаптева // Материалы XVIII Международной летней школы-семинара по современным проблемам теоретической и математической физики. - 2006. - С. 47.

5. Лаптева, А. В. Индексная вектор-функция / А. В. Лаптева // Материалы XVIII Международной летней школы-семинара по современным проблемам теоретической и математической физики. - 2006.

- С. 48-52.

6. Lapteva, А. V. Index Vector-Function and Minimal Cycles / A. V. Lapteva, E. I. Yakovlev // Lobachevskii Journal of Mathematics. - 2006.

- Vol. 22. - P 35-46.

7. Лаптева, А. В. Алгоритм поиска минимальной одномерной цепи в заданном классе относительных гомологий / А. В. Лаптева // Вестник ННГУ. Серия Математика. - 2006. - Вып. 1(4). - С. 59-64.

8. Лаптева, А. В. Поиск минимальных одномерных циклов триангулированного многообразия / А. В. Лаптева // Современные вопросы геометрии и механики деформируемого твердого тела. Тезисы региональной научной конференции. - Чебоксары, 2006. - С. 25-26.

9. Lapteva, А. V. Minimal 1-Cycles Generating a Canonical Basis

of 2-Manifold's Homology Group / A. V. Lapteva, E. I. Yakovlev // International Journal of Pure and Applied Mathematics. - 2006. - Vol. 31, No 4. - P. 555-570.

10. Лаптева, А. В. Построение дуального базиса из минимальных циклов / А. В. Лаптева // Труды матем. центра им. Н.И. Лобачевского. - 2006. - Т. 34. - С. 151-152.

11. Лаптева, А. В. Поиск минимальных относительных циклов на многообразиях с краем / А. В. Лаптева // Чебоксары: Чувашгоспед-инстытут. Вестник. - 2006. - N 5. - С. 96-100.

11одпнсано к печат и ■ __

Форма! 60x90 1/16 усл. неч л. 0,?S Тираж 100 чкч. Заказ №

I ОУ В! 10 «Нижеюродский государственный архитектурно-строительный университет» 60V)5Q. Н. Новюрод. Ильинская ул.. 65._

11олиграфическии центр ННГАСУ М)3')50, II. Новгород. Ильинская \л , 65.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Лаптева, Анастасия Владимировна

Введение

1 Исследуемые объекты и используемые конструкции

§ 1.1. Полиэдры. Симплициальные отображения и действия групп. Триангулированные многообразия.

§ 1.2. Группы гомологий.

§ 1.3. Барицентрические звезды и индексы пересечения

§ 1.4. Способы задания полиэдров. Обозначения входных данных.

§ 1.5.Коллапсирование. Алгоритм.

§ 1.6.Двумерные замкнутые многообразия. Канонический и полуканонический базисы Ях (Р).

2 Индексная вектор-функция и накрытия

§ 2.1.Индексация относительно заданного (п — 1)-мерного цикла и вычисление индексов пересечения.

§ 2.2.Индексная вектор-функция и ее свойства

§ 2.3.Накрытия в терминах симплициальных схем

§ 2.4.Построение регулярного накрытия с группой автоморфизмов G = Hi(P).

§ 2.5. Свойства построенного накрытия.

3 Минимальные пути и циклы

§ 3.1. Весовые функции. Примеры.

§ 3.2. Поиск минимального пути с заданным индексом, соединяющего заданные вершины.

§ 3.3.Минимизация пути с заданными концами и индексом на многообразии.

§ 3.4. Минимизация пути из заданной вершины до заданного множества.

§ 3.5.Построение минимальных циклов.

§ 3.6. Построение дуального базиса из минимальных циклов

4 Двумерный случай. Приложения

§ 4.1.Вычисление базисных 1-циклов 2-многобразия без применения матриц инциденций.

§ 4.2.Построение минимальных циклов, порождающих канонический базис

§ 4.3. Выделение ручек и устранение топологического шума

Введение диссертация по математике, на тему "Минимальные циклы в заданных классах гомологий"

В последние два десятилетия сформировалась и активно развивается вычислительная топология, в которой соединяются два различных, хотя и связанных друг с другом направления. Первое - это использование компьютерных методов при решении тех или иных проблем самой топологии, например, классификации компактных трехмерных многообразий ([19]—[23], [60]-[63]). Второе направление можно обозначить как приложения топологии к задачам, связанным с компьютерным моделированием и компьютерной графикой.

Настоящая работа в большей степени относится ко второму из указанных направлений.

Существует много работ, в которых предлагаются различные подходы к вычислению топологических характеристик и элементов полиэдров. Можно отметить классический алгоритм для вычисления групп гомологий и их базисов произвольного симплициального комплекса, основанный на приведении матриц инциденций к нормальной диагональной форме ([5], [32]). В работах [39], [51], [56] предлагались различные его модификации.

Для поверхностей известен ряд методов, основанных на использовании представления ее в виде канонического многоугольника. Так, в работах [65], [59] предложен алгоритм поиска базиса одномерной группы гомологий замкнутой поверхности. С помощью канонического представления решаются задача построения базиса фундаментальной группы поверхности из петель минимальной длины ([40]) и задача определения гомотопности двух заданных кривых ([45], [46], [47]).

В работах [41], [49] разработан алгоритм вычисления групп гомологий трехмерного симплициального комплекса, основанный на построении триангуляции Делоне. Другой метод решения аналогичной задачи предложен в серии работ [42], [43], [44].

Нематричным методам поиска циклов, порождающих базисы групп гомологий для двумерных многообразий, посвящены работы [6], [34], [35], [52].

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

Большая серия работ связана с применениями в вычислительных алгоритмах дискретного аналога теории Морса ([37], [38], [48], [50], [64], [66]). В частности, на основе подобных методов в [54], [67] предлагается один из способов устранения топологического шума, то есть топологических дефектов компьютерных моделей.

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

Построенная в диссертации индексная вектор-функция позволяет решать подобную [45], [46] задачу о гомологичности двух заданных одномерных цепей для любого n-мерного замкнутого многообразия.

Отметим, что в [36] приведен алгоритм индексации и основанный на нем метод поиска минимальных циклов в заданном классе абсолютных гомологий [х] € Н\{Р) ориентируемого замкнутого 2-многообразия Р. Но указанный алгоритм существенно использует двумерность многообразия Р и двусторонность простых одномерных циклов в Р и потому в общей ситуации неприменим.

Целью работы является разработка методов решения следующих задач:

1) индексация ребер триангулированного замкнутого п-мерного многообразия Р относительно заданного (п — 1)-мерного цикла г 6

Z„i(P); Л

2) построение симплициального регулярного накрытия р : Pj ->• Р с группой накрывающих преобразований G = Н\{Р)\

3) поиск цепей с Е С\{Р)) минимизирующих весовую функцию L : С\(Р) —> К на заданном подмножестве группы Ci(P);

Методы исследования. Использованы методы алгебраической и кусочно-линейной топологии, теории графов.

Научная новизна.

Все результаты работы, выносимые на защиту, являются новыми и получены автором самостоятельно.

1. Предложен способ индексации одномерных симплексов триангулированного замкнутого многообразия Р относительно заданного цикла г € Zn-\(P). С его помощью строится гомоморфизм Jz : С\(Р) Z2, позволяющий вычислить индекс пересечения z с любым одномерным циклом полиэдра Р, а также индексная вектор-функция J : С\(Р) -У 1Т2 относительно базиса [г"-1],., [zгруппы гомологий Hn-i(P).

2. Построена симплициальная схема полиэдра Pj, симплициаль-но и регулярно накрывающего многообразие Р с группой накрывающих преобразований G = Н\{Р).

3. Разработаны методы минимизации весовой функции L : Ci(P) 1 на следующих подмножествах группы С\(Р) замкнутого многообразия Р:

• на множестве путей, соединяющих фиксированные вершины и имеющих заданный индекс;

• на множестве одномерных цепей, соединяющих вершину и многообразия Р с некоторым подполиэдром Q С Р и образующих класс относительных гомологий [х] Е Н\(Р, {и} U Q);

• на произвольном ненулевом гомологическом классе [ж] G Нг(Р).

4. Указан способ построения минимальных циклов, порождающих базис группы #i(P), дуальный заданному базису группы Нп-г(Р).

Апробация. Описанные результаты работы были обнародованы на международной научной конференции "Актуальные проблемы математики и механики"(Казань, 26 сентября - 1 октября 2004 г.); на всероссийских молодежных научных школах-конференциях "Лобачевские чтения" (Казань, 2005г., 2006г.); на международных летних школах-семинарах по современным проблемам теоретической и математической физики "Петровские чтения" (Казань, 2005г., 2006г.); на III международной конференции по прикладной математике (Пловдив, Болгария, 12-18 августа 2006 г.); на региональной научной конференции "Современные вопросы геометрии и механики деформируемого твердого тела" (Чебоксары, 19-20 октября 2006г.); на научных семинарах по геометрии и топологии кафедры геометрии и высшей алгебры ННГУ (рук. доц. Н.И. Жукова и проф. Е.И. Яковлев, 2005г., 2006г.); на научном семинаре кафедры компьютерной топологии и алгебры Челябинского госуниверситета (рук. член-корр. РАН С.В. Матвеев, 2006г.).

Публикации и вклад автора. Результаты диссертации опубликованы в работах [8]-[16], [57], [58]. Отдельно этот список приведен в конце заключения. В совместных статьях [8], [9],[57],[58] научному руководителю Е.И. Яковлеву принадлежат постановка задачи и общее руководство работой. Все теоремы и их доказательства получены автором диссертации.

Краткое содержание работы.

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

Заключение диссертации по теме "Геометрия и топология"

Выход: циклы z{,., z\.

Описание алгоритма.

Шаг 1. Построение индексной функции. С помощью алгоритма 2.1 вычислим индексную вектор-функцию J : С\(Р) —У Щ, относительно базиса [а^],.,

Шаг 2. Построение полуканонического базиса [zj],. ., [z}}. Шаг 2.1. Положим q := 1.

Шаг 2.2. Если q = г — 1, то положим zq := xlq, := xlq+l и перейдем к шагу 3.

Шаг 2.3. Положим z* := xlq и р := q + 1.

Шаг 2.4. Если Ind(a;p, xlq) = Jq{Xp) = 1, то перейдем к шагу 2.6.

Шаг 2.5. Присвоим переменной р значение р+1 и повторим шаг

2.4.

Шаг 2.6. Вычислим определитель матрицы Bq, составленной из индексов пересечения Ind^1, ж]) = J3(x\), i,j G {q + 1,., г} \ {p}. Если detSg = 0, то вернемся к шагу 2.5. Иначе положим zq+1 := xlp.

Шаг 2.7. При р > q+1 положим xlp := xq+1, q := q+2 и вернемся к шагу 2 2.

Шаг 2.8. Переставим компоненты Jk, к = 1,.,г индексной вектор-функции J = (J1,., Jr) в соответствии с новым порядком циклов в базисе.

Шаг 3. Построение канонического базиса. Для всех к = 1,., г выполним шаги 3.1 - 3.5.

Шаг 3.1. Положим М = L(zl).

Шаг 3.2. Из последовательности S = {1,.,г} удалим элемент А;, а из оставшихся элементов получим подпоследовательность 5* = {«ij • • •, V-1} С S. Построим гомоморфизм Л : С\(Р) Z^-1, полагая = Jlq для всех q = 1,., г — 1.

Шаг 3.3. При четном к положим к* = к — 1, z* = z\v в противном случае положим к* — к, z* = 4+1 • Построим индекс I £ И2 1 по следующему правилу: Ik* := 1, Р := 0 для j £ {1,., г - 1} \ {А;*}.

Шаг 3.4. Для каждой вершины v £ У выполним цикл 3.4.1 - 3.4.3.

Шаг 3.4.1. С помощью алгоритма Дейкстры составим список К вершин и £ V(P), удовлетворяющих неравенству cIl(v, и) < М/2 (см. (3.3)). Из симплексов, все вершины которых лежат в К, построим подполиэдр Р* С Р.

Шаг 3.4.2. Применяя алгоритм 3.1, либо построим цикл zv £ Zi(P#) с формальным индексом J*(zv) = I, проходящий через вершину v и имеющий наименьший вес L(zv) < М среди всех циклов, обладающих аналогичными свойствами, либо придем к выводу о его несуществовании.

Шаг 3.4.3. Если цикл zv будет найден, то положим z\ = zv и М = L(zv).

Шаг 3.5. С помощью алгоритма 2.1 пересчитаем к-ую компоненту вектор-функции J.

Конец алгоритма.

Теорема 4.2. Алгоритм 4-2 корректен. Гомологические классы циклов z\,., z\, полученных с помощью алгоритма 4-2, образуют канонический базис группы гомологий Н\(Р), а вес каждого цикла z\, к = 1,., г, минимален среди всех циклов, ему гомологичных.

Доказательство. Предположим, что либо q = 1, либо 1 < q = 2n + 1 < г и с помощью шага 2 алгоритма 4.2 из набора {х\,., жг} выбраны такие циклы z\,.,z\n, что Ind(z2Z1,z^) — 1 для всех I = 1 ,.,п. Рассмотрим матрицу Bq, составленную из индексов пересечения Ъ13 = Ш(х1п+г,xln+J), i,j € {l,.,r - 2п}, циклов ж*,., zj, не вошедших в набор {zj,., zln}. При этом, в силу невырожденности формы Ind на Hi(P) и согласно шагу 2.6, det Bq = 1.

Заметим, что матрица Bq является кососимметрической. Поэтому г—9+1 \ 2 detBi= (^Е , (4-2) где Uij - алгебраическое дополнение минора 2-го порядка, расположенного на пересечении столбцов и строк матрицы Bq с номерами 1 и j ([24], глава 1, §12). Из условия det Bq ф 0 следует, что, по крайней мере, одно из слагаемых в разложении (4.2) отлично от нуля. Пусть р' - номер этого слагаемого и р = q + p'. Тогда Ind(a^, х*) = 1 и det Bq+2 ф 0, где матрица Bq+2 получена из матрицы Bq вычеркиванием столбцов и строк с номерами 1 и р' = р — q.

Таким образом, построение полу канонического базиса корректно. Отметим важное обстоятельство. Для всех q = 1,3, .,г — 1 матрица Aq, составленная из индексов пересечения циклов zq,.,zl после завершения шага 2, получается из Bq перестановкой строк и столбцов. Поэтому det Aq = det Bq = 1.

Пусть с помощью шага 3 алгоритма 4.2 преобразованы первые к циклов z\,., z\, к Е {1,., г}. Покажем, что после этого гомологические классы циклов z\,.,z\ останутся линейно независимыми.

Согласно 3.1 - 3.5, после преобразования циклов z\,.,zl матрица Aq индексов пересечения всех циклов приводится к виду где I = maх{к,к*}, q = I -f 1, а звездочкой обозначены элементы матрицы Aq. При четном к имеют место равенства к = I и = аг1 = 0 для всех = q,., г.

Очевидно, det Лд = det Akq2- Пользуясь разложением вида (4.2), отсюда и из (4.3) получим равенство det Aq = det А* = det Поскольку det^9 = 1, то этим линейная независимость гомологических классов [z{],., [z*] доказана.

Таким образом, в случае к < г после шага 3.5 мы снова получим корректно определенную индексную вектор-функцию J и можем повторить цикл 3.1-3.5 для следующего значения параметра к.

В ситуации, когда к = г, матрица Aq имеет канонический вид. Следовательно, после завершения работы алгоритма 4.2 гомологические классы циклов z\,. образуют канонический базис группы #х(Р).

Пусть далее к £ {1,., г}, у Е ZX(P) и [у] = [z\], где z\ - цикл, полученный после завершения работы алгоритма. Рассмотрим индексную вектор-функцию J относительно базиса группы Е\ (Р), построенного перед шагом 3.1 для выбранного к. Тогда J(y) = J{z\), а значит, и J*(y) = J*{z\) = I

То, что цикл z\ имеет минимальный вес среди циклов z Е Z\(P)

О 1 . О 0 0 . О ^ 1 0 . О 0 0 . О

О 0 . О 1 0 . О

О 0 . 1 0 Щд . щг О 0 . О aqi * . *

4.3) / с формальным индексом «Д {z) — /, следует из построения на шаге 3.4 (см. теорему 3.4). Сокращая на шаге 3.2 индексную вектор-функцию J : С\{Р) —> Ъ\ до гомоморфизма Л : С\(Р) —> Z^-1, мы находим минимальный цикл в объединении двух гомологических классов. Тогда тем более найденный цикл минимален в своем классе гомологий.

Замечание 4.2. Построение канонического базиса группы гомологий Hi (Р) двумерного замкнутого ориентируемого многообразия Р - более сильный результат, чем нахооюденис базиса группы Н\(Р), дуального заданному базису группы #ni(P) (алгоритм 3.5), поскольку канонический базис дуален самому себе.

Рис. 4.2: Слева - 4 базисных цикла одномерной группы гомологий кренделя, выделенные разными цветами, справа - минимальные циклы, порождающие канонический базис одномерной группы гомологий.

4.3. Выделение ручек и устранение топологического шума

Пусть Р - триангулированное замкнутое и ориентируемое 2-многообразие рода т и Т{Р) - список его треугольников. Выделением ручки мы называем составление такого списка T(R) С Т(Р), что объединение R всех его элементов гомеоморфно ограниченному цилиндру, а объединение симплексов из дополнения Т(Р) \ T(R) представляет собой поверхность Р' рода га — 1с двумя компонентами края.

Предлагаемая схема выделения всех ручек поверхности Р состоит в следующем:

1. С помощью алгоритма 4.1 найдем циклы ., yr, г = 2га = rank Hi (Р), гомологические классы которых образуют базис группы

UP)

2. Воспользуемся алгоритмом 2.1 и вычислим индексную вектор-функцию Jo : Ci(P) —> относительно базиса [yi],., [уг] группы

UP)

3. Применяя алгоритм 4.2, построим циклы zi,. ,zr, каждый из которых имеет минимальный вес в своем классе гомологий, а эти классы образуют канонический базис группы Hi(P) При этом, согласно шагу 3.6, мы получим также индексную вектор-функцию J : Ci(P) 1Т2 относительно базиса [z\],., [zr].

4. Для каждой пары циклов Z2k-i и Z2k, к = 1,., га, выполним следующие шаги:

4.1. Выберем основной цикл х G {z2k—1) %2к} и дополнительный цикл у £ {z2jfc-i, *2к}, У ф X (например, по длине).

4.2. Для каждой вершины уг, i = 1,., щ, основного цикла х в одномерном остове накрывающего полиэдра Pj найдем кратчайший путь уг, идущий из вершины (vt, 0) в вершину (г;,, J(y)), и положим

Уг=Р{Уг)

4.3. Начиная с треугольника, инцидентного ребру [vtvt+i] (г + 1 вычисляется по модулю пк), построим список Тг треугольников, расположенных между циклами уг и уг+1. Для объединения 11г симплексов из Тг вычислим группу

4.4. Построим максимальное по включению сильно связное объединение Rk областей Ut, для которых rankHi(Ut) ^ 1.

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

При устранении топологического шума наиболее сложной и интересной является задача локализации и удаления лишних ручек. Если выделенная ручка Rk является дефектом компьютерного моделирования, то исправление модели осуществляется удалением соответствующего ручке списка треугольников Tk(Rk) из общего списка Т(Р) и заклеиванием получающихся двух дыр.

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

Пусть yi,yi+1,. ,yi> - циклы, вошедшие в ручку Rk, 1 ^ I < V ^ пк, и п - целая часть числа (I' — /)/2. Обозначим символом S(Rk) список {п + 1, п - 1, п + 2, п — 2,., /} при нечетном I' — I и список {п + 1, п — 1, п + 2, п — 2,., /, /'} при четном I' — I. Для каждого j из S(Rk) с помощью шага 3.2 построим проходящий через вершину Vj цикл у' не имеющий общих ребер с уп и с циклами у',, построенными до у'у Символом R'k обозначим объединение треугольников, расположенных между циклами у[ и y'v, содержащее ручку Rk.

Удаление области R'k приводит к более качественному результату, чем при разрезании поверхности по одному приближенно кратчайшему нестягиваемому циклу на данной ручке или по двум близким к нему циклам ([65]).

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

Рис. 4.3: Модель "Счастливый Будда". Пример ручки, являющейся дефектом моделирования.

Для проверки алгоритмов удобно использовать модели полученные в лаборатории компьютерной графики Стэнфордского университета с помощью 3D сканера, например, модель "Счастливый Будда". Указанная модель содержит 543652 вершины, 1087716 треугольников, 104 ручки, из которых только 5 - настояттще.

Рис. 4.4: Выделение и удаление лишней ручки.

Заключение

Основными результатами диссертации, выносящимися на защиту являются следующие:

1. Предложен способ индексации одномерных симплексов триангулированного замкнутого многообразия Р относительно заданного цикла z Е Zn-i(P). С его помощью строится гомоморфизм Jz : Ci(P) —У Z2, позволяющий вычислить индекс пересечения z с любым одномерным циклом полиэдра Р, а также индексная вектор-функция J : С\{Р) Z£ относительно базиса [z"-1],., [z"-1] группы гомологий Нп-\(Р).

2. Построена симплициальная схема полиэдра Р/, симплициаль-но и регулярно накрывающего многообразие Р с группой накрывающих преобразований G = Н\ (Р).

3. Разработаны методы минимизации весовой функции L : С\{Р) -> R на следующих подмножествах группы С\{Р) замкнутого многообразия Р:

• на множестве путей, соединяющих фиксированные вершины и имеющих заданный индекс;

• на множестве одномерных цепей, соединяющих вершину и многообразия Р с некоторым подполиэдром Q С Р и образующих класс относительных гомологий [ж] Е #i(P, {u} U Q);

• на произвольном ненулевом гомологическом классе [ж] Е Я,(Р).

4. Указан способ построения минимальных циклов, порождающих базис группы #i(P), дуальный заданному базису группы

Hn-i(P).

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

4. Лаптева, А. В Метод устранения топологического шума в компьютерных моделях ЗБ-объектов / А. В. Лаптева // Материалы XVIII Международной летней школы-семинара по современным проблемам теоретической и математической физики. - 2006. - С. 47.

6. Lapteva, А. V. Index Vector-Function and Minimal Cycles / A. V. Lapteva, E. I. Yakovlev // Lobachevskii Journal of Mathematics. -2006. - Vol. 22. - P. 35-46.

9. Lapteva, А. V. Minimal 1-Cycles Generating a Canonical Basis of 2-Manifold's Homology Group / A. V. Lapteva, E. I. Yakovlev // International Journal of Pure and Applied Mathematics. - 2006. - Vol. 31, No 4. - P. 555-570.

11. Лаптева, А. В. Поиск минимальных относительных циклов на многообразиях с краем / А. В. Лаптева // Чебоксары: Чуваш-госпединститут. Вестник. - 2006. - N 5. - С. 96-100.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Лаптева, Анастасия Владимировна, Нижний Новгород

1. Ахо, А. В. Структуры данных и алгоритмы / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман. - М-СПб.- Киев: Изд. дом "Вильяме", 2001.

2. Бредон, Г. Введение в теорию компактных групп преобразований / Г. Бредон. М.: Наука, 1980.

3. Дольд, А. Лекции по алгебраической топологии / А. Дольд. -М.: Мир, 1976.

4. Дубровин, Б. А. Современная геометрия. Методы теории гомологий / Б. А. Дубровин, С. П. Новиков, А. Т. Фоменко. М.: Наука, 1984.

5. Зейферт, Г. Топология / Г. Зейферт, В. Трельфалль. M.-JI.: ГОНТИ, 1938; Ижевск: НИЦ РХД, 2001.

6. Зинченко, В. Ю. Новый метод построения базисных циклов групп гомологий полиэдров / В. Ю. Зинченко // Труды Математического центра имени Н.И. Лобачевского. 2003. - Т. 21. - С. 118-120.

7. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. М.: МЦНМО, 2001.

8. Лаптева, А. В. Методы поиска кратчайших 1-циклов в заданном классе гомологий / А. В. Лаптева, Е. И. Яковлев // Труды матем. центра им. Н.И. Лобачевского. 2004. - Т. 25. - С. 159— 160.

9. Лаптева, А. В. Алгоритмы для поиска минимальных одномерных циклов / А. В. Лаптева, Е. И. Яковлев // Вестник ННГУ. Серия Математика. 2005. - Вып. 1(3). - С. 76-87.

10. Лаптева, А. В. Поиск минимального пути в заданном классе относительных гомологий / А. В. Лаптева // Труды матем. центра им. Н.И. Лобачевского 2005. - Т. 31. - С. 88-89.

11. Лаптева, А. В. Метод устранения топологического шума в компьютерных моделях ЗБ-объектов / А. В. Лаптева // Материалы XVIII Международной летней школы-семинара по современным проблемам теоретической и математической физики. -2006. С. 47.

12. Лаптева, А. В. Индексная вектор-функция / А. В. Лаптева // Материалы XVIII Международной летней школы-семинара по современным проблемам теоретической и математической физики. 2006. - С. 48-52

13. Лаптева, А. В. Алгоритм поиска минимальной одномерной цепи в заданном классе относительных гомологий / А. В. Лаптева // Вестник ННГУ. Серия Математика. 2006. - Вып. 1(4). - С. 59-64.

14. Лаптева, А. В. Поиск минимальных одномерных циклов триангулированного многообразия / А. В. Лаптева // Современные вопросы геометрии и механики деформируемого твердого тела Тезисы региональной научной конференции. Чебоксары, 2006. - С. 25-26.

15. Лаптева, А. В. Построение дуального базиса из минимальных циклов / А. В. Лаптева // Труды матем. центра им. Н.И. Лобачевского. 2006. - Т. 34. - С. 151-152.

16. Лаптева, А. В. Поиск минимальных относительных циклов на многообразиях с краем / А. В. Лаптева // Чебоксары: Чуваш-госпединститут. Вестник. 2006. - N 5. - С. 96-100.

17. Липский, В. Комбинаторика для программистов / В. Липский. М.: Мир, 1988.

18. Масси, У. Алгебраическая топология. Введение / У. Масси, Д. Столлингс. М.: Мир, 1977.

19. Матвеев С. В., Алгоритм распознавания трехмерной сферы (по А. Томпсон) / С. В. Матвеев // Математический сборник. -1995. Т. 186. N 5. - С. 69-84.

20. Матвеев, С. В. Алгоритмическая классификация 3-многообразий. Проблемы и результаты / С В. Матвеев // Труды Математического института имени В.А. Стеклова. -1999. Т. 225. - С. 264-275.

21. Матвеев, С. В. Алгоритмические и компьютерные методы в трехмерной топологии / С. В. Матвеев, А. Т. Фоменко. М.: Изд-во МГУ, 1991, 1998.

22. Матвеев, С. В. Компьютерная классификация расширенных диаграмм Хегора / С. В. Матвеев, В. В. Таркаев // Вестник Челябинского университета. Серия 3. Математика, механика, информатика. 2003. - N 2. - С. 146-152.

23. Матвеев, С. В. Табулирование трехмерных многообразий / С. В. Матвеев // Успехи математических наук. 2005. - Т. 60. N 4. - С. 97-122.

24. Окунев, JI. Я. Высшая алгебра / JI. Я. Окунев. М.: ОНТИ НКТП СССР, 1937.

25. Рохлин, В. А. Начальный курс топологии. Геометрические главы / В. А. Рохлин, Д. Б. Фукс. М.: Наука, 1977.

26. Рурк, К. Введение в кусочно линейную топологию / К. Рурк, Б. Сандерсон. М.: Мир, 1974.

27. Свитцер, Р. М. Алгебраическая топология гомотопии и гомологии / Р. М. Свитцер. - М.: Наука, 1985.

28. Спеньер, Э. Алгебраическая топология / Э. Спеньер. М.: Мир, 1971.

29. Стинрод, Н. Топология косых произведений / Н. Стинрод. М.: ИЛ, 1953.

30. Стинрод, Н. Основания алгебраической топологии / Н Стинрод, С. Эйленберг. М.: ИЛ, 1956.

31. Фоменко, А. Т. Наглядная геометрия и топология. Математические образы в реальном мире / А. Т. Фоменко. М.: Изд-во МГУ, 1992.

32. Фоменко, А. Т. Курс гомотопической топологии / А. Т. Фоменко, Д. Б. Фукс. М.: Наука, 1989.

33. Цишанг, X. Поверхности и разрывные группы / X. Цишанг, Э. Фогт, X. Д. Колдевай. М.: Наука, 1988.

34. Яковлев, Е. И. Быстрые алгоритмы вычисления групп гомологий и их базисов / Е. И. Яковлев, П. А. Гордиенко // Материалы VII Международного семинара "Дискретная математика и ее приложения". 2001. - С. 284 - 287.

35. Яковлев, Е. И. Алгоритмы для вычисления базисных циклов одномерной группы относительных гомологий / Е. И. Яковлев, О. В. Логинов // Вестник ННГУ. Серия Математика. 2003. -Вып. 1. - С. 132 - 142.

36. Яковлев, Е. И. Вычислительная топология / Е. И. Яковлев. -Нижний Новгород: Изд-во ННГУ, 2005.

37. Axen, U. Computing Morse functions on triangulated manifolds / U. Axen // Proceedings of the SIAM Symposium on Discrete Algorithms (SODA). 1999. - P. 850-851.

38. Axen, U. Auditory morse analysis of triangulated manifolds / U. Axen, H. Edelsbrunner // Mathematical Visualization. Berlin, 1998. - P. 223-236.

39. Chao, J. Cubical singular simplex model for 3D objects and fast computation of homology groups / J. Chao, J. Nakayama // Proc. IEEE. 1996. - P. 190-194.

40. Colin de Verdiere, E. Optimal System of Loops on an Orientable Surface / E. Colin de Verdiere, F. Lazarus // Proceedings of the 43rd Annual IEEE Symposium of Foundations of Computer Science. 2002. - P. 627-636.

41. Delfinado, C. An incremental algorithm for betti numbers of sim-plicial complexes on the 3-sphere / C. Delfinado, H. Edelsbrunner // Comput. Aided Geom. Design. 1995. - Vol. 12. - P. 771-784.

42. Dey, Т. К. Computational topology / Т. К. Dey, Н. Edelsbrunner, S. Guha // Advances m Discrete and Computational Geometry. -Providence, 1998. P. 109-143.

43. Dey, Т. K. Algorithms for Manifolds and Simplicial Complexes in Euclidean 3-Space / Т. K. Dey, S. Guha // Proc. 28th ACM Sym-pog. Theory Comput. 1996. - P. 398-407.

44. Dey, Т. K. Computing Homology Groups of Simplicial Complexes in R3 / Т. K. Dey, S. Guha // Proceedings ot 28th Symposium of Theory of Computing. 1996. - P. 397-407.

45. Dey, Т. K. Optimal algorithms for curves on surfaces / Т. K. Dey, S. Guha // Proc. 35th IEEE Ann. Sympos. Found. Comput. Sci. -1995. P. 266-274.

46. Dey, Т. К Transforming Curves on Surfaces / Т. K. Dey, S. Guha // J. Comput. Sys. Sci. 1999. Vol. 58. - P. 297-325.

47. Dey, Т. K. A New Technique To Compute Polygonal Schema for 2-Manifolds with Application to Null-Homotopy Detection / Т. K. Dey, H. Schipper // Disc. & Сотр. Geom. 1995. - Vol 14. - P. 93-110.

48. Edelsbrunner, H. Morse-Smale Complexes for Piecewise Linear 3-Manifolds / H. Edelsbrunner, J. Harer, V. Natarajan, V. Pascucci // Proceedings of the 19th Annual ACM Symposium of Computer Geometry. New York, 2003. P. 98-101.

49. Edelsbrunner, H. Topological Persistence and Simplification / H. Edelsbrunner, D. Letscher, A. Zomorodian // Disc. Comput. Geom. 28. 2002. - P 511-533.

50. Forman, R. A discrete morse theory for cell complexes / R. Forman // Geometry, Topology and Physics for Raoul Bott. International Press. 1994. - P. 112-125.

51. Friedman, J. Computing Betti numbers via combinatorial Lapla-cians / J. Friedman // Proc. 28th ACM Sympos. Theory Comput.- 1996. P. 386-391.

52. Gu, X. Geometry Images / X. Gu, S. J. Gortler, H. Hoppe // Proc. SIGGRAPH'02. New York, 2002. - P. 355 - 361.

53. Guskov, I. Topological Noise Removal / I. Guskov, Z. Wood // Graph. Interf. 2001. - P. 19-26.

54. Hayat-Legrand, C. Computer calculation of the degree of maps into the Poincare homology sphere / C. Hayat-Legrand, S. Matveev, H. Zieschang // Experimental Mathematics. 2001. - Vol. 10. No. 4.- P. 497-508.

55. Kannan, R. Polynomial algorithms for computing the Smith and Hermite normal forms of integer matrix / R. Kannan, A. Bachem // SIAM Jour.Сотр. 1979. - Vol. 8. - P. 499-507.

56. Lapteva, A. V. Index Vector-Function and Minimal Cycles / A. V. Lapteva, E. I. Yakovlev // Lobachevskii Journal of Mathematics.- 2006. Vol. 22. - P. 35-46.

57. Lapteva, A. V. Minimal 1-Cycles Generating a Canonical Basis of 2-Manifold's Homology Group / A. V. Lapteva, E. I. Yakovlev // International Journal of Pure and Applied Mathematics. 2006. -Vol. 31, No 4. - P. 555-570.

58. Lazarus, F. Computing a Canonical Polygonal Schema of an Ori-entable Triangulated Surface / F. Lazarus, M. Pocchiola, G. Vegter, A. Verroust // Proc. 17th Annu. ACM Sympos. Comput. Geom. -2001. P. 80-89.

59. Matveev, S. V., Algorithmic classification of 3-manifolds and knots / S. V. Matveev // Gazette des Mathematiciens. 2001. - No. 89. - P. 49-61.

60. Matveev, S. V. Computer classification of 3-manifolds / S. V. Matveev // Russian Journal of Mathematical Physics. 2000. -Vol. 7. No. 3. - P. 319-329.

61. Matveev, S. V. Computer presentation of 3-manifolds / S. V Matveev // Lecture Notes in Computer Science. 2001. - Vol. 2243 "Digital and Image Geometry: Advanced Lectures". - P. 59-74.

62. Matveev, S. V., Computer recognition of three-manifolds / S. V. Matveev // Experimental Mathematics. 1998. - Vol. 7. No. 2. -P. 153-161.

63. Shinagawa, Y. Surface coding based on morse theory / Y. Shina-gawa, T. L. Kunii, Y. L. Kergosien // IEEE Computer Graphics and Applications. 1991. - Vol. 11. No. 5. - P. 66-78.

64. Vegter, G. Computational Complexity of Combinatorial Surfaces / G. Vegter, С. K. Yap // Proceedings of the 6th Annual Symposium on Computational Geometry. 1990. - P. 93-111.

65. Wood, Z. Semi-Regular Mesh Extraction from Volumes / Z. Wood, M. Desbrun, P. Schroder, D. Breen // Proceedings of Visualization. 2000. - P. 275-282.

66. Wood, Z. Removing Excess Topology From Isosurfaces / Z. Wood, H. Hoppe, M. Desbrun, P. Schroder // ACM Transactions on Graphics. 2004. - Vol. 23, No 2. - P. 190 - 208.