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

Введение

Глава 1. Аппроксимации информационных множеств

1.1 Основные определения.

§1 Постановка задачи.

§2 Круги обнаружения.

§3 Область неопределенности

§4 Остаточная область

§5 Общая упреждающая область

§6 Общая следящая область.

1.2 Аппроксимация информационных множеств.

§1 Аппроксимация области неопределенности.

§2 Построение вспомогательных множеств Vik-ы

§3 Аппроксимация общей остаточной области.

§4 Аппроксимация общей упреждающей области

§5 Свойства аппроксимаций информационных множеств

Глава 2. Алгоритмическая реализация

2.1 Теоретико-множественные операции на плоскости.

§1 Способы компьютерного представления множеств.

§2 Класс представимых на компьютере множеств.

§3 Структуры данных для представления границ множеств

§4 Решение вспомогательных задач.

§5 Вычисление характеристической функции.

§6 Реализация теоретико-множественных операций.

§7 Операция r-расширения множества.

§8 Регуляризованная аппроксимация г-расширения.

§9 Упрощение границы множества.

2.2 Теоремы вложения для информационных множеств

§1 Свойства регуляризованных операций.

§2 Регуляризованная аппроксимация области неопределенности.

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

Глава 3. Методы решения поисковых задач

3.1 Визуализация процесса поиска.

3.2 Расчет достаточных ресурсов.

§ 1 Расчет минимального радиуса круга обнаружения.

§2 Расчет минимальной скорости

3.3 Поиск в монотонном многоугольнике

§1 Патрулирование горизонтального сечения монотонного многоугольника.

§2 Вытеснение уклоняющегося объекта.

§3 Достаточные условия для поиска в монотонном многоугольнике.

§4 Алгоритм построения поисковой траектории.

§5 Сравнение с другими методами.

3.4 Поиск в кольце.

§1 Поиск в кольце.

§2 Изменение направления вытеснения в многоугольнике

§3 Поиск в многоугольной области

§4 Оптимизация поиска.

§5 Дальнейшее развитие.

Существует огромное количество постановок задач поиска, охватывающих почти все аспекты человеческой деятельности. Общей чертой всех поисковых задач является связь с получением определенной информации о предмете поиска. Например, в монографии Р. Айзекса [1] задачи поиска рассматриваются как дифференциальные игры с неполной информацией. Первые исследования поисковых задач проводились в основном в военных целях, но в дальнейшем полученные результаты нашли гораздо более широкое применение. В настоящее время имеется достаточно много подходов к решению задач поиска в разнообразной постановке, но о создании единой теории поиска говорить пока нельзя.

Данная работа посвящена задачам поиска объектов. В работе А.Г. Чхартишвили и Е.В. Шикина [2] выделены основные элементы, свойственные почти всем задачам поиска объектов: поисковая область, объекты поиска, ищущие объекты и условия обнаружения.

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

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

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

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

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

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

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

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

Задачи поиска неподвижного объекта рассматривались JI.A. Петросяном [3, 4] и Р. Айзексом [1]. Уклоняющийся объект выбирает точку области поиска, в которой он будет находиться, а ищущий объект выбирает траекторию движения с целью минимизации времени сближения с уклоняющимся на заданное расстояние. Решение игры ищется в смешанных стратегиях; оптимальная стратегия уклоняющегося заключается в равновероятном выборе точки области поиска.

Решению задач поиска ищущего объекта с детерминированным движением посвящена книга Д.П. Кима [5], в которой рассматривается равномерное и прямолинейное движение уклоняющегося объекта. Уклоняющийся объект выбирает свое начальное положение и параметры движения; частично эта информация может быть известна ищущему.

В работе А.Г. Чхартишвили и Е.В. Шикина [2] рассматривается задача, где областью поиска является вся плоскость. Уклоняющийся объект выбирает свое начальное положение и направление движения. Затем он движется равномерно и прямолинейно со скоростью, известной ищущему. Ищущий обладает преимуществом в скорости, но ему неизвестно ни начальное положение, ни направление движения уклоняющегося объекта. При этих предположениях найдена стратегия действий ищущего, гарантирующая обнаружение уклоняющегося вне зависимости от выбранной им стратегии.

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

Искомый объект может использовать информацию о поведении ищущих объектов для активного уклонения от обнаружения. Такие задачи динамического поиска рассматриваются в работах JI.A. Петросяна [3, 4], Е.В. Шикина и А.Г.Чхартишвили [2]. Данная работа также посвящена решению задач этого типа.

В рассматриваемых здесь задачах участвуют один уклоняющийся и несколько ищущих объектов, представляющие собой точки, перемещающиеся в некотором подмножестве евклидова пространства, обозначаемом Q и называемом областью поиска. Объекты обладают простым движением и способны произвольно менять направление движения в любой момент времени. Скорость уклоняющегося объекта не может превосходить известной постоянной /3. Ищущие объекты перемещаются с постоянными скоростями cti, не меньшими /3. Поиск продолжается до обнаружения уклоняющегося объекта. Критерием обнаружения является сближение уклоняющегося объекта с одним из ищущих на расстояние, не превышающее заданную для данного ищущего постоянную называемую радиусом круга обнаружения i-то ищущего.

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

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

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

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

Для исследования и решения задач динамического поиска в областях, имеющих нетривиальную структуру, оказалось целесообразным в дополнение к аналитическим применять и геометрические методы. Одним из перспективных является геометрический подход, предложенный Е.В. Шикиным, С.М. Губайдуллиным и А.Г. Чхартишвили, который заключается в построении изменяющихся во времени вспомогательных подмножеств области поиска, называемых информационными и отражающих степень информированности участников поиска в каждый момент времени [2,7-12,14,15]. Среди информационных множеств могут быть выделены четыре основных класса (точные определения будут даны в первой главе):

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

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

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

• Следящие области, являющиеся объединениями остаточных и упреждающих областей.

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

Более того, траекторию ищущего объекта можно выбрать так, чтобы круг обнаружения захватывал расширяющуюся границу области неопределенности [2]. При заданном соотношении параметров (в этом примере (3/а = 1/12) и сравнительно небольшом радиусе начальной области неопределенности такая траектория представляет собой сходящуюся к точке А спираль; движение ищущего объекта приводит к постепенному уменьшению области неопределенности. К моменту достижения ищущим объектом точки А уклоняющийся объект будет гарантированно обнаружен.

Обзор результатов, полученных при геометрическом подходе к решению поисковых задач, и список литературы даны в работе [2]. Геометрический подход был использован и при решении задачи поиска одним ищущим объектом на некоторых классах замкнутых поверхностей [10] и в двух- и трехмерных выпуклых областях [11, 12]. Были найдены достаточные условия существования поисковых траектории и описаны

Рис. 1: Пример информационных множеств методы построения таких траекторий.

Вопрос о необходимых условиях осуществимости поиска, также как вопрос о построении оптимальных траекторий, пока остаются открытыми. В работе П.М. Ларина [13] получены необходимые условия для некоторых постановок задач поиска, но пока они далеки от достаточных.

Информационные множества для случая нескольких ищущих объектов рассматривались лишь в небольшом числе работ (см. [2, 14, 15]). Также мало изучен вопрос поиска в невыпуклых областях. Это связано с тем, что при увеличении количества ищущих объектов или при усложнении структуры области поиска трудности при построении информационных множеств значительно возрастают. В таких случаях аналитические методы построения информационных множеств перестают быть эффективным и разумно воспользоваться вычислительными и графическими возможностями современных компьютеров.

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

Рекуррентные формулы для аппроксимаций информационных множеств с обоснованием их свойств рассматриваются, например, в работах П.М. Ларина [14, 15]. В диссертационной работе приведены и обоснованы рекуррентные формулы для области неопределенности, остаточной и упреждающей областей на заданных временных промежутках в задаче поиска с участием нескольких ищущих объектов. В этих формулах широко применяются теоретико-множественные операции и операция r-расширения множества [16], поэтому для проведения вычислений по предлагаемым формулам необходима алгоритмическая схема реализации теоретико-множественных операций.

Вопросам разбиения плоскости кривыми Безье и алгоритмической реализации операций над множествами на плоскости посвящены работы В.А. Дебелова, A.M. Мацокина и С.А. Упольникова [17-19]. В этих работах классические теоретико-множественные операции заменяются на регуляризованные или логические, широко применяемые в системах геометрического моделирования и автоматического проектирования. Применение регуляризованных операций позволяет избежать появления множеств, границы которых будут включать разрезы или изолированные точки и отрезки прямых. Однако класс множеств, рассмотренный в этих работах, не замкнут относительно г-расширения множества. Другая схема алгоритмической реализации операций над множествами, предложенная А.А. Скворцовым [20], допускает применение классических теоретико-множественных операций и является замкнутой относительно операции r-расширения множества.

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

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

На основе идей, приведенных в работах [19] и [24], создана алгоритмическая схема реализации операций над множествами на плоскости, использующая только целочисленную арифметику и не подверженная влиянию ошибок округления. Применение целочисленной арифметики приводит к тому, что граница допустимых, т.е. представимых на компьютере, множеств строится только из отрезков прямых. Допустимое множество не может содержать разрезы, а в состав его границы не могут входить изолированные точки и отрезки. Для того чтобы класс допустимых множеств был замкнут относительно операций объединения, пересечения и дополнения, вместо классических теоретико-множественных операций рассматриваются регуляризованные операции над множествами. Результат r-расширения допустимого множества далеко не всегда является допустимым множеством, поэтому операция r-расширения также заменяется на регуляризованную аппроксимацию.

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

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

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

Разработанные численные методы применяются для решения трех типов задач поиска.

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

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

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

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

Задача построения траектории в монотонном многоугольнике применяется для обоснования достаточных условий осуществимости поиска и построения поисковых траекторий двух ищущих объектов в кольце и в многоугольной кольцевой области.

Диссертация состоит из введения и трех глав. Главы разбиты на разделы, некоторые разделы разбиты на параграфы, нумерация которых начинается заново в каждом разделе. Текст иллюстрируется рисунками. Нумерация формул, теорем, утверждений и рисунков - сквозная по всей диссертации.

1. Айзеке Р. Дифференциальные игры. М., Мир, 1967.

2. Чхартишвили А.Г., Шикин Е.В. Динамический поиск объектов. Геометрический взгляд на проблему // Фундаментальная и прикладная математика, 1995, Т.1, Вып.4, С.827-862.

3. Петросян Л.А., Зенкевич Н.А. Оптимальный поиск в условиях конфликта. Л., 1987.

4. Петросян Л.А., Гарнаев А.Ю. Игры поиска. СПб., Издательство Санкт-Петербургского университета, 1992.

5. Ким Д.П. Методы поиска и преследования подвижных объектов. М., Наука, 1989.

6. Хеллман О. Введение в теорию оптимального поиска. М., 1985.

7. Губайдуллин С.М. Следящая область в задачах поиска. М., Деп. в ВИНИТИ, 1992, №2020-В92.

8. Губайдуллин С.М., Шикин Е.В. Следящие области на цилиндре и на торе // Вестник московского университета. Сер. 15. Вычислительная математика и кибернетика, 1992, №2, С.46-50.

9. Чхартишвили А.Г., Шикин Е.В. Метод следящих областей в задачах поиска // Математический сборник, 1993, Т.184, №10, С. 107-134.

10. Чхартишвили А.Г., Шикин Е.В. Динамические задачи поиска и обнаружения на некоторых замкнутых поверхностях // Дифференциальные уравнения, 1993, Т.29, №11, С.1948-1957.

11. Скворцов А.А. Динамический поиск в плоской выпуклой области. М., Деп. в ВИНИТИ 10 ноября 1995 г., №2985-В95.

12. Скворцов А.А. Динамический поиск в трехмерных выпуклых областях // Вестник московского университета. Сер. 15. Вычислительная математика и кибернетика, 1999, №3, С.20-24.

13. Ларин П.М. О неразрешимости задач гарантированного поиска в достаточно большой области // Вестник Московского университета, Сер. 15, Вычислительная математика и кибернетика, 2000, №1, С. 44-47.

14. Ларин П.М. Упреждающая область, порождаемая парой ищущих, и ее визуализация. М., Деп. в ВИНИТИ, 1995, №2910-В95.

15. Ларин П.М. Следящая область пары отрезков // Фундаментальная и прикладная математика, 1998, Т.4, Вып.2, С.559-566.

16. S.E.O. Saeed, A. de Pennington, J.R. Dodsworth. Offsetting in Geometric Modelling // Computer Aided Design, Vol. 20, No. 2.

17. Дебелов В.А., Мацокин A.M., Упольников С.А. Разбиение плоскости кривыми Безье / / Труды 7-ой международной конференции по компьютерной графике и визуализации Графикон'97 (21-24 мая 1997, Москва), Протвино, 1997, С.67-74.

18. Дебелов В.А., Мацокин A.M., Упольников С.А. Разбиение плоскости и теоретико-множественные операции // Сибирский журнал вычислительной математики / РАН. Сибирское отделение, Новосибирск, 1998, Т.1, №3.

19. Дебелов В.А., Мацокин A.M. Алгоритм реализации теоретико-множественных операций // Труды 8-ой международной конференции по компьютерной графике и визуализации Графикон'98 (7-11 сентября 1998, Москва), ВМК МГУ, 1998, С. 174-181.

20. Скворцов А.А. Алгоритмическая реализация теоретико-множественных операций на плоскости. М., Деп. в ВИНИТИ 10 июля 2000 г., ДО1915-В00.

21. Березин И.С., Жидков Н.П. Методы вычислений. М., Государственное издательство физико-математической литературы, 1960.

22. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М., Наука, 1987

23. Дж. X. Уилкинсон. Алгебраическая проблема собственных значений. М., Наука, 1970

24. Kokichi Sugihara, Masao Iri. A Solid Modelling System Free from Topological Inconsistency. // Journal of Information Processing, Vol. 12, No. 4, 1989.

25. Березин С.Б. Теоретико-множественные операции в задаче визуализации переменных информационных множеств. М., Деп. в ВИНИТИ, 2000, М27-В00.

26. Березин С.Б. Информационные множества в задаче динамического поиска объектов с несколькими ищущими // Вестн. Моск. ун-та. Сер. 15, Вычислительная математика и кибернетика, №3, 2001.

27. Березин С.Б. Геометрия и графика динамического поиска объектов // Интеллектуальные системы, Т. 6, вып. 1-4, 2001.

28. Березин С.Б. Решение задачи динамического поиска в монотонном многоугольнике. М., Деп. в ВИНИТИ, 2002, №1330-В2002.

29. Аджиев В., Пасько А., Савченко В., Сурин А. Моделирование форм с использованием вещественных функций // Открытые системы, №5, 1996

30. Бродин В.В., Шагурин И.И., Микропроцессор i486. Архитектура, программирование, интерфейс. М., Диалог-Мифи, 1993

31. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. М., Диалог-Мифи, 1995

32. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональная модели. М., Диалог-Мифи, 2000

33. Jihad El-Sana, Amitabh Varshney. Topology Simplification for Polygonal Virtual Environments. // IEEE Transactions on Visualization and Computer Graphics, Vol. 4, No. 2, April-June 1998

34. Rolf Klein, Adrzej Lingas. Fast skeleton construction // European Symposium on Algorithms 1995, C.585-592