Геодезический подход к расчету информационных множеств в задачах динамического поиска

6. Краснощекое П. С., Морозов В. В., Попов Н. М. Оптимизация в автоматизированном проектировании. М.: МАКС Пресс, 2008.

7. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал Пресс, 2008.

8. Тихонов А.Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1986.

9. Тихонов А.Н., Леонов A.C., Ягола А.Г. Нелинейные некорректные задачи. М.: Наука, 1995. 10. Васильев Ф. П. Методы оптимизации. М.: Факториал Пресс, 2002.

Поступила в редакцию 14.02.09

УДК 519.67

П.А. Воронин1

ГЕОДЕЗИЧЕСКИЙ ПОДХОД К РАСЧЕТУ ИНФОРМАЦИОННЫХ МНОЖЕСТВ В ЗАДАЧАХ ДИНАМИЧЕСКОГО ПОИСКА

Предложен новый метод расчета информационных множеств в задачах динамического поиска. Представление множеств основано на аппарате полей расстояний, а операции над ними — на вычислении геодезических расстояний при помощи нахождения вязкостного решения уравнения Гамильтона^Якоби. Описанный метод применяется для решения поисковых задач на поверхностях в трехмерном пространстве.

Ключевые слова: динамический поиск, поля расстояний, геодезические расстояния.

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

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

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

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

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

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

В зависимости от задачи поведение искомых объектов может быть разным. Объекты могут быть неподвижными или перемещающимися, причем движение может быть детерминированным (принадлежать какому-то классу [4]), стохастическим [5] или уклоняющимся (когда объект активно препятствует нахождению [6]). Могут отличаться и информационные возможности объектов (их осведомленность о выбранной стратегии и параметрах движения противодействующей стороны). Мы будем рассматривать случай, когда искомые объекты активно уклоняются от ищущих, местоположение, скорость и стратегия движения которых в каждый момент времени им известны, в то время как ищущие знают только максимальную скорость уклоняющихся. Ищущим необходимо выбрать такую стратегию поведения, которая бы гарантировала нахождение искомых объектов вне зависимости от их действий. Эту

1 Факультет ВМиК МГУ, асп., e-mail: pavel.voroninQgmail.com.

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

Наиболее хорошо изучены задачи поиска уклоняющихся объектов в случае областей, представляющих собой подмножества евклидова пространства — двухмерного (например, круг [3], монотонный многоугольник [7], кольцо [7]) или трехмерного (например, поверхность цилиндра и тора [8] или шар [9]). Оказалось, что уже на таких простых областях аналитические методы исследования малопрактичны и громоздки. Во многом более эффективным показал себя геометрический подход, разработанный в начале 1990-х годов Е.В. Шикиным, С.М. Губайдуллиным и А.Г. Чхартишвили. Общая идея методов этого типа заключается в построении вспомогательных информационных множеств, соответствующих сведениям, накапливаемым в процессе поиска ищущими и уклоняющимися объектами друг о друге. Обширный обзор работ по данной теме дан в работе [3].

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

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

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

Информационные множества показали себя как крайне эффективный инструмент при решении задач динамического поиска как в двух-, так и в трехмерном случае (см., например, [7, 8, 9]), и даже на плоскости Лобачевского [10].

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

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

Было предложено два подхода к построению численных методов расчета информационных множеств: 1) в работе [7] был предложен метод для двухмерного случая, основанный на представлении поискового множества набором отрезков, аппроксимирующих его границу; 2) в работе [12] предложено использовать неявное представление множеств при помощи полей расстояний [13] и показано, как при его посредстве решать задачу на плоскости и в трехмерном пространстве.

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

ых

б

Рис. 1. Информационные множества: остаточная область

ности, на случай поверхностей в трехмерном пространстве). Для вычисления геодезических расстояний в таких областях мы воспользовались аппаратом численного решения уравнений Гамильтона-Якоби [14].

2. Общая схема численных методов. Рассмотрим общую схему построения численных методов для расчета остаточной области [7]. Для простоты начнем с двухмерной, неограниченной области поиска, одного ищущего и одного уклоняющегося объектов, движущихся с постоянными скалярными скоростями.

Введем следующие обозначения. Пусть скалярная скорость уклоняющегося объекта равна ?7, а скорость ищущего объекта — V (будем считать, что V > ?7, т. е. ищущий имеет преимущество по скорости). Пусть область обнаружения ищущего — круг радиуса Р, а траектория его перемещения P(t). Нам нужно рассчитать изменение переменной остаточной области A(t) на отрезке времени от t = 0 до t = Т.

Для начала дискретизируем задачу. Приблизим заданную траекторию ломаной, проходящей через точки P0,Pb ... ,РП, где Pi — положение ищущего в момент времени ti = ¿At, At = T/n. Будем последовательно искать остаточные области Aq, Ai, ..., Ап = А, где Ai = A(ti). На рис. 2 изображены первые три остаточные области: Aq, А\ и

Рис. 2. Остаточные области: Ао

Область Ад, начальное состояние нашей системы, — это круг В(Ро;Я) радиуса Я с центром в точке Ро (рис. 2, а): в начальный момент времени ¿о об уклоняющемся объекте можно сказать только то, что он находится не ближе, чем на расстоянии радиуса обнаружения от ищущего объекта.

Область А\ устроена немного сложнее. За время At ищущий объект переместился в точку Р\. Поскольку скорость уклоняющегося объекта меньше скорости ищущего, то области А\ принадлежат все круги, в которые уклоняющийся объект за это время не мог успеть добраться: Р(Р(£о + т); Я — т£У), О ^ г ^ At. Как несложно проверить [15], объединение всех таких кругов дает фигуру, изображенную на рис. 2, б (подобные фигуры будем называть фигурами А-типа и обозначать как А(С\, С2, Рь ^2)5 где Сг — центры, а Р^ — радиусы образующих кругов; Я\ может равняться нулю). Итак, А1 = А(Р0,Рьг,Р), г = Р- Д[/, Аи = Д£ • [/.

За время At круг Ао = Р(Р0;Р) сузился до круга Р(Р0;г). Легко видеть, что для фигур типа А(С\, С2, Рь ^2) сужение дает фигуру того же типа. Имеем (рис. 2, в): А2 = А(Р0,Р1,г — Д?7, г) и и А(РьР2,Г,Р).

Общая формула описания фигур А& выглядит так:

A0 = B(P0;R),

Ак+1 = Offset (Л*, -AU) U A(Pk,Pk+1,r, R).

Здесь Offset (А, —г) — сужение множества А на полосу шириной г (эту операцию иногда еще называют "r-расширением" с отрицательным г).

Полученная формула легко обобщается на случай нескольких ищущих объектов. Пусть г-му объекту соответствует траектория Тогда

N ...

" Г, Г.

Ак+1 = Offset^*,-AU) U

г=1

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

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

Вернемся к общему случаю. Нетрудно заметить, что формулы (1)-(3) не содержат операций, которые были бы характерны исключительно для плоскости. И действительно, все они остаются верными при переходе как к трехмерным поисковым задачам [12], так и к задачам поиска на поверхностях. Единственное, что при этом меняется, — это интерпретация множеств B(P;R), А(С\, Сг, i?i, R2) и Offset(A, ±г), под которыми теперь понимаются соответствующие аналоги круга, фигуры на рис. 2, б и r-расширения соответственно.

3. Методы, основанные на использовании полей расстояний. Итак, для широкого класса поисковых задач возможно приближенное рекуррентное вычисление информационных множеств по формулам (1)-(3). Заметим, что для реализации численного метода на их основе нам необходимо в каждом случае выбирать такое программное представление множеств, которое позволяло бы эффективно проводить над ними следующие четыре базовые операции: объединение, пересечение, разность и г-расширение.

В работе [12] в качестве такого представления предложено неявное задание множеств, известное как функциональное представление (Function Representation, F-Rep [16]) или поле расстояний (Distance Field, DF [13]). Стоит отметить, что хотя операции их инициализации и рендеринга по времени сравнительно затратны, зато многие операции редактирования (включая теоретико-множественные операции и r-расширение) просчитываются чрезвычайно быстро [13, 16]. Более того, как будет показано ниже, к полям расстояний применим аппарат быстрого вычисления геодезических расстояний.

Вместо заданного замкнутого геометрического объекта будем рассматривать порождаемое им в пространстве скалярное поле, значение которого в произвольной точке равно расстоянию от этой точки до границы объекта, взятому со знаком плюс, если точка лежит вне объекта, и со знаком минус в противном случае. Например, для круга радиуса единица с центром в начале координат поле расстояний DF будет задаваться формулой DF(x,y) = \Ji? + у2 — 1.

Поле расстояний фигуры X будем обозначать как DFx, поверхность (линию) уровня у этого поля — как ISO„ DFх .

Перечислим некоторые свойства полей расстояний.

1. Граница дС породившей поле расстояний DFc фигуры С в точности совпадает с нулевой поверхностью (линией) уровня DFc'-

3. Пусть у нас есть поля расстояний Ш*^ и БРВ, порожденные фигурами А и В соответственно. Тогда верны следующие формулы:

дС = /ЯОоШ^с = {(ж, у) : ЯРс(я,у) = 0}. 2. Через поверхности уровня можно выразить и границу г-расширения для С:

ОАЬе^С, г) = 130ГРРС = {(ж, у) : РРс(х,у) = г} = /5О0(^с - г).

A U В = ISO0(mm(DFA, DFB)), А П В = ISOQ(m&Ti(DF.4, DFB)) A = ISOo(-DFa), А\В = An В = ISOo(max(DFA,-DFB)).

Для дополнительной устойчивости вместо min и тах можно использовать более гладкие R-функции высокого порядка [16].

4. Заметим также, что хотя DFomet(C,r) = DFc^r и DF= —DF а, но DFaub Ф min(£>F^, DFb), DFаг\в Ф va.&3L.(DFA,DFв), DF А\в Ф max^i*1a,—DFв)- Другими словами, в общем случае формулы п. 3 позволяют вычислять границу фигуры, получающейся в результате применения теоретико-множественных операций, но не поле расстояний для этой фигуры.

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

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

Ак+1 = ISO0(DFAk + AU)DA(Pk,Pk+1,r,R), Ак+1 = ISO^mmiDF Ак + AU,DF А(Рк,Рк+1,г,К)))-

Получим следующую последовательность действий (DF-алгоритм):

1) l)l-\M = DFAk + AU,

2) DFupd = DFА(рк,рк+иг,п)-,

3) DFnew = min(DFold,DFupd),

4) DFAk+1=DFISooDFne„.

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

Реализация этого алгоритма для случая подмножеств плоскости и трехмерного пространства описана в статье [12].

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

Пусть в трехмерном евклидовом пространстве задана некоторая простая поверхность М и ее регулярная параметризация ф. Пусть на этой поверхности задана некоторая регулярная кривая j(t), t G [0,1]. Длина этой кривой вычисляется по формуле

1 1 l(7) = ьф(7) = I\фът dt = J ^(ттушюя,

о о

где 1ф — матрица первой квадратичной формы [17].

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

D(A,B)= min L(j).

7СМ,7(0)=.4,7(1)=Б

Функционалом длины для множества точек S = {хк}к=1 С М называется функция Us(x) =

= minD(x,xk), х G M. Имеет место следующая теорема [18, 19].

к

Теорема. Для любого множества S = {xk}%=1 С М функционал длины есть единственное вязкостное решение уравнения эйконала

/И™*11 = 1,

\Us(xl) = 0Vk.

Рассмотрим теперь численные методы вычисления функционала длины. Пусть даны сетка, некоторое подмножество S ее вершин и требуется найти значение функционала длины Us во всех узлах этой сетки.

Наиболее распространенным подходом к отысканию функционала длины является численное решение уравнения (4) посредством одной из модификаций метода быстрого движения (Fast Marching, FM [14]). Алгоритмы этого метода основаны на идее распространения волны, т.е. таком порядке вычислений, при котором каждый узел сетки обрабатывается ровно один раз. Использование этого подхода обосновано монотонностью задачи: значение функционала длины в каждом узле зависит от (и может быть вычислено исходя из) его значений лишь в нескольких соседних узлах, причем эти значения не больше вычисляемого.

По ходу алгоритма каждый узел х последовательно получает следующие метки l(x): 1) Far — узел еще не был обработан, значение не определено; 2) Front — узел находится в процессе обработки, известно некоторое приближение функционала длины в этой точке Us(x) « U(x); 3) Computed — узел обработан и больше рассматриваться не будет, значение функционала длины в данном узле вычислено.

Для работы FM-алгоритму необходимы три ключевые компоненты.

1. Процедура х —> Neigh(x) вычисления множества соседей каждого узла.

2. Функция оценки приоритета Р(х) вершин с меткой Front. На каждой итерации обрабатывается вершина с наименьшим приоритетом. В большинстве случаев в качестве функции приоритета берут текущую оценку расстояния2: Р(х) = U(x).

3. Процедура х ^ Update(x) вычисления нового значения поля в узле на основе некоторого количества точных и приближенных значений поля в соседних узлах. Эта процедура обычно представляет собой какую-либо численную схему для локального решения уравнения (4). Чаще всего это обратно-поточная схема [21, 22] или одна из ее устойчивых модификаций [23, 24].

Общая схема FM-алгоритма такова.

1. Инициализация: VieS: U{x) = 0, 1{х) = Front, Vy g S : l (у) = Far.

2. Выбор точки: x = arg min P(z).

z:l(z)=Front

3. Метка: l(x) = Computed.

4. Обновление соседей: для всех у € Neigh(x):

если l(y) = Far, то l(y) = Front, U(y) = Update(y); если l(y) = Front, то U(y) = mm(U(y), Update(y)); вычислить новый приоритет P(y).

5. Останов: если {z : l(z) = Front} = 0, то повторить 2.

При использовании эффективной структуры данных для хранения множества Front-вершин сложность алгоритма составляет 0(nlog(n)). На практике алгоритм ведет себя почти линейно. В статье [25] приводится модификация FM-алгоритма, в которой при помощи квантования приоритета удается добиться снижения теоретической сложности до оптимальной 0(п).

5. Геодезический поиск. Опишем реализацию Ш-'-алгоритма для построения остаточной области на поверхности в трехмерном пространстве.

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

2. В соответствии с первой строкой системы (1) для нахождения фигуры Ао необходимо вычислить поле расстояний круга с заданным центром и радиусом: Ш*1 в(С;Я)(х) = ВРс(%) — -й- Оно выражается

2 В задаче нахождения геодезической кривой для пары точек можно воспользоваться эвристиками типа .4*. существенно ускоряющими вычисления [20].

через поле расстояний для центра круга, а поле расстояний для точки есть ее функционал длины. Значит, его можно найти при помощи РМ-алгоритма. Заметим, однако, что в классическом варианте при помощи алгоритма быстрого движения можно найти функционалы длины только для точек, являющихся узлами сетки. Если же точка С попадает внутрь треугольника сетки или на его ребро, понадобится предварительно сделать подразбиение сетки (рис. 3, а). Отметим, что подразбиение делается лишь на время вычисления РРс(х), а затем сетка возвращается в исходное состояние.

а б в

Рис. 3. Подразбиение сетки: по точке (а); по отрезку (б); по линии

уровня

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

А(Рь, Рк+1-) г, Р)- Сначала рассмотрим случай г = Я. Тогда А(Рь, Рк+1-> Щ — Р{Р{^)->Р)->

т.е. А(Рь, Р&+1, Я, Я) — Д-расширение отрезка [Рк-)Рк+1]. Значит, его можно вычислить как поверхность уровня Я его функционала длины. Для приближенного нахождения функционала длины отрезка подразобьем по нему сетку, т.е. поступим так же, как в предыдущем пункте (рис. 3, б). Получим набор точек отрезка (и одновременно узлов сетки) = для которых посредством алгоритма быстрого движения вычислим £/9*. Имеем ~ [/5* — Д. Заметим, что РРА(рк,рк+1,я,я) — РР— Я = тт(РР31 — Я). Это означает, что верно следующее приближение:

А(Рк, Рк+1, Я-, Я) ~ 130о(ттВРВ(3. Возвращаясь к общему случаю, по аналогии имеем

г г'

А(Рк,Рк+иг,Я) « /5О0(тт№в(5г)Гг)), где гг = г + (Я - г)-^—Щ-

г \Рк+1-Рк\

Таким образом, мы выразили границу фигуры А(Рк, Рк+1, т, Я) через поверхность уровня некоторого поля, правда, нам пока неизвестно ее поле расстояний.

Рис. 4. Пример работы алгоритма

4. На четвертом шаге РР-алгоритма и в конце предыдущего пункта требуется вычислять поле расстояний для области К, граница которой задана нулевой изолинией некоторого поля, К = 1вОо^О, а значит, состоит из отрезков, вершины которых лежат на ребрах сетки. Как в пунктах 2, 3, подразобьем сетку по этим отрезкам (рис. 3, в) и получим набор точек изоповерхности = являющих-

ся узлами новой сетки. При помощи алгоритма быстрого движения посчитаем для них функционал длины £/9*. Чтобы превратить полученную функцию в поле расстояний, остается только сделать ее отрицательной внутри области К. Легко видеть, что для этого достаточно установить ее знак равным знаку исходного поля:

врк = sgn(^}).[/s*.

На рис. 4 приводится пример остаточной области, построенной описанным алгоритмом для поисковой траектории, заданной на торе.

Дополнительные цветные анимированные иллюстрации, демонстрирующие работу данного алгоритма, доступны на сайте автора [26].

СПИСОК ЛИТЕРАТУРЫ

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

2. Петроеян J1. А., Зенкевич Н. А. Оптимальный поиск в условиях конфликта. J1.: Изд-во ЛГУ, 1987.

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

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

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

6. Петроеян J1. А., Гарнаев А. Ю. Игры поиска. СПб.: Изд-во СПбГУ, 1992.

7. Берез и н С. Б. Графический подход к исследованию и решению задач динамического поиска: Дис. ... канд. физ.-мат. наук. М., 2002.

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

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

10. Чхартишвили А. Г., Шикин Е. В. Следящая область в пространстве Лобачевского // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. 1994. № 2. С. 36-41.

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

12. Воронин П. А. О новом подходе к расчету и визуализации информационных множеств в задачах динамического поиска // Труды 18-й Междунар. конф. по комп. графике и зрению ГрафиКон'2008. М.: ООО "ИНТУИТ.ру", 2008. С. 184-191.

13. Payne В., Toga A. Distance field manipulation of surface models // Сотр. Graphics and Appl. 1992. 12. N 1. P. 65-71.

14. Set hi an J. Level Sets Methods and Fast Marching Methods. 2nd ed. Cambridge University Press, 1999.

15. Чхартишвили А. Г. Метод следящих областей в задачах динамического поиска: Дис. ... канд. физ.-мат. наук. М., 1994.

16. Pasko A., Adzhiev V., Sourin A., Savchenko V. Function representation in geometric modeling: concepts, implementation and applications // The Visual Computer. 1995. 11. N 8. P. 429-446.

17. Погорелов А. В. Дифференциальная геометрия. M.: Наука, 1974.

18. Курант Р. Уравнения с частными производными. М.: Мир, 1964.

19. Lions P. L. Generalized solutions of Hamilton-Jacobi equations. London: Pitman, 1982.

20. Peyre G., Cohen L. Heuristically driven front propagation for fast geodesic extraction // Int. J. for Comput. Vision and Biomech. 2007. 1. N 1.

21. Kimmel R., Sethian J. Computing geodesic paths on manifolds // Proc. Nat. Acad. Sci. 1998. 95. N 15. P. 8431-8435.

22. Peyre G., Cohen L. Geodesic methods for shape and surface processing // Advances in Comput. Vision and Medical Image Processing: Methods and Applications / Ed. by J. M. R. S. Tavares, R. M. Natal Jorge. Springer, 2008.

23. Spira A., Kimmel R. An efficient solution to the eikonal equation // Interfaces and Free Boundaries. 2004. 6. N 3. P. 315-327.

24. Bronstein A., Bronstein M., Kimmel R. Weighted distance maps computation on parametric three-dimensional manifolds // J. of Comput. Physics. 2007. 225. N 1. P. 771-784.

25. Yatziv L., Bartesaghi A., Sapiro G. O(N) implementation of the fast marching algorithm // J. of Comput. Physics. 2006. 212. N 2. P. 393-399.

26. http://www.primaler.ru/cg/

Поступила в редакцию 01.12.08