Моделирование многомерных объектов и методы полиномиальной оптимизации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Яшина, Марина Витальевна

• Яшина, Марина Витальевна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Яшина, Марина Витальевна

Введение.

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

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

Глава 1. Использемые результаты высшей алгебры.

Глава 2. Расстояние от эллипсоида до линейного многообразия.

2.1. Условия пересечения.

2.2. Нахождение расстояния.

2.3. Нахождение ближайших точек поверхностей.

2.4. Расстояние от точки до эллипсоида.

2.5. Расстояние от (п — 1)-мерной плоскости до элипсоида

2.6. Некоторые свойства полинома Т{г).:.

Глава 3. Расстояние от эллипсоида до квадрики.

3.1. Условия пересечения.

3.2. Нахождение расстояния.

3.3. Нахождение ближайших точек поверхностей.

3.4. Программная реализация алгоритмов.

3.5. Вычислительные эксперименты.

Введение диссертации (часть автореферата) на тему «Моделирование многомерных объектов и методы полиномиальной оптимизации»

Постановка задачи, ее значение, обзор предшествующих исследований

Алгебраическая геометрия pi геометрическое моделирование имеют дело с кривыми и поверхностями в IRn, заданными полиномиальными (алгебраическими) уравнениями. Алгебраическая геометрия исследует теоретические свойства алгебраических кривых и поверхностей; геометрическое моделирование использует полиномиальные, кусочно-полиномиальные и дробно-рациональные функции для построения компьютерных моделей механических компонент при конструировании промышленных объектов и производств [29].

Среди множества математических задач, возникающих в этом разделе вычислительной геометрии (computational geometry), одной из важнейших является

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

2) задача установления наличия пересечения этих многообразий — что соответствует, например, столкновению движущихся объектов (collision detection) и

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

Решение общей задачи вычисления расстояния между алгебраическими многообразиями, заданными в Мп системами уравнений вида

9i{X) = 0,., 9к(Х) = 0 при X = хп / при полиномиальных д\,.достаточно просто в случае многообразий линейных. Так, к примеру, растояние от точки Хо 6 до многообразия

СТХ — Н при С = Си . с1т ^

021 • • • С2т

Л^ Кп ) пхт у Сп\ . • . Спт у предполагается, что т < п и что ранг матрицы С равен ш; здесь и далее Т означает транспонирование; расстояние понимается в евклидовой метрике) определяется по формуле

I =

1е1 Ст • С СГХ0 - Н

V (СГХ0 ну О det(Cт • С) т.е. фактически сводится к решению квадратного уравнения [26].

Формула для расстояния между двумя линейными многообразиями в ]КП также известна в литературе. Пусть линейные многообразия в К" заданы параметрически

X = + АЛ + . + ХкХк и У = У0 + Д1У1 + . + при {Ах,., /¿1,., [11} С М и при фиксированных столбцах

Х0) Х\,., Хк, Уо, У1;., С Мп.

Составим из этих столбцов матрицы

Р = [Хи ., Хк, Ух, • ■ •, Уе]пх(к+е) и

Р = [^ъ ■ • • > Хк, Уъ • ■ •> Уе, Х0 - Уо]пх(^+1) •

Тогда расстояние вычисляется по формуле

1еЬ(Рт • Р) det(Pт • Р)

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

ХТАХ + 2ВТХ -1 = 0 при фиксированных симметричной матрице А и столбце В £ Мп. Практическая же важность этой задачи обусловлена тем обстоятельством, что, например, в случае п = 3 эллипсоиды оказались наиболее простыми геометрическими объектами, подходящими для моделирования множеств и физических тел в молекулярной физике, геодезии, приборостроении, компьютерной графике (особенно в задачах компьютерного зрения (computer vision))[31]. В n-мерном пространстве эллипсоиды возникают естественным образом в задаче классификции (кластеризации) данных. При описании объекта набором из п признаков, каждая серия их измерений задает точку в параметрическом пространстве. При недостоверности результатов измерений, каждую из точек можно рассматривать как аппроксимацию объекта, самым простым приближением которого может считаться эллипсоид (который может быть интерпретирован как эллипсоид рассеяния из математической статистики) [7, 11]. Однако отсутствие общего алгоритма нахождения расстояния от точки до эллипсоида в Мп приводит к тому, что при расчетах вместо точного расстояния используется его приближенная оценка (например, расстояние Махалонобиса).

В идеологии решения общей задачи нахождения расстояния между гладкими поверхностями лежит вариационный принцип трансверсальности: кратчайшее расстояние между этими поверхностями достигается на их общей нормали (см. §54 книги [10]). В случае поверхностей, заданных алгебраическими уравнениями, этот принцип дает возможность использовать метод множителей Лаграпжа. Так, к примеру, для задачи вычисления расстояния между двумя квадриками в М3, заданными алгебраическими уравнениями

ХтАгХ + 1В\Х -1 = 0

1) и

ХтА2Х + 2В\Х -1 = 0, (2) функция Лагранжа будет иметь вид

Х% У, Ах, Л2) = (X - У)Т(Х - У) - Х^АгХ + 2ВГ{Х -1) -- А2(УтА2У + 2£2тУ-1), а соответствующая система: дГ 2 [(X — У) — \1{АгХ + В0] = О, = 2 [(У — X) — \2{А2Х + В2)} = О, = - [ХГА1Х + 2В\Х — 1] = 0, ^ дх = - [УгА2У + 25;гУ — 1] = 0. ар

9У ар алх дР1

3)

Требуется найти решения этой системы относительно векторов {X, У} С К3, обеспечивающих минимум целевой функции

X - У)Т{Х - У).

Система (3) является нелинейной алгебраической относительно входящих в нее неизвестных: каждое из 8 ее уравнений является квадратным. Для решения подобных систем имеются два подхода: первый основан на применении приближенных методов решения систем нелинейных уравнений; все подобные методы представляют из себя модификации метода Ньютона. В этом русле велись исследования [39, 40]. К достоинствам такого подхода следует отнести быструю сходимость итераций к экстремуму целевой функции, к недостаткам — традиционное для ньютоно-подобных методов отсутствие гарантии того, что найденный экстремум обеспечивает глобальный минимум целевой функции. В подтверждении этого произведем качественную оценку потенциально возможной ситуации. В главе 3 будет показано, что система (3) имеет, как правило, 24 решения, в общем случае комплексных. Таким образом, имеется не более 24 потенциально возможных результатов итерационных процедур для произвольных стартовых значений итерационного процесса. Если бы применение итерационного метода дало с необходимой точностью все 24 вещественных решения, то задача поиска расстояния была бы решена однозначно. Однако вещественность всех решений системы (3) вовсе не гарантирована (см. пункт 2.6), так что после нахождения какого-то одного из этих решений мы не можем быть уверены, что отсутствует другое, более оптимальное. Это обстоятельство отмечается во всех исследованиях, посвященных разработке итерационного подхода: в некоторых случаях удается установить эмпирически (с помощью вспомогательных оценок) сходимость метода к истинному решению, обеспечивающему минимум целевой функции. Тем не менее, универсальных рекомендаций, подходящих для любой задачи, нет.

В связи с отмеченными выше недостатками итерационных методов, в последние 20 лет стал активно развиваться альтернативный подход, основанный на алгебраических методах исключения переменных в алгебраических системах. Возвращаясь к системе (3), такой подход позволяет свести систему из нескольких уравнений от нескольких переменных к одному уравнению от одной переменной. При этом гарантирована абсолютная достоверность полученного результата: это обеспечивается тем, что аналитические алгоритмы используют только точную арифметику рациональных чисел; так что отсутствуют ошибки округления. Аналитические методы требуют достаточного развития компьютерных мощностей (они более ресурсоемки, чем итерационные) и разработки вспомогательных пакетов символьных вычислений (так, на с. 83 будет показано, что даже в случае, когда уравнения исходных поверхностей имеют коэффициенты в пределах трех десятичных знаков, "окончательное" уравнение имеет коэффициенты из чуть менее 200 цифр; и эту ситуацию следует считать нормой!). Тем не менее, уровень развития современных персональных компьютеров, а также таких прикладных пакетов как МАРЬЕ, МАТНЕМАТ1СА, МАСБУМА, МиРАБ и других позволяет решать подобные задачи за вполне обозримое время. Так что постепенно аналитический подход становится все более и более конкурентноспособным по сравнению с численным; это обстоятельство заметно из сравнения количеств публикаций, посвященных каждому из этих подходов.

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

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

ХтАгХ + 2В\X -1 = 0, ХТА2Х + 2В\Х -1 = 0 (4) не должна иметь вещественных решений. При размерности пространства п большей двух, система (4) является недоопределенной и поиск ее вещественных решений (или, хотя бы, доказательство факта их существования или отсутствия) становится нетривиальной задачей.

В работах [36, 44, 45] эта задача исследовалась только для случая п = 3 и в следующем частном случае: требовалось установить условия возможности разделения поверхностей с помощью плоскости. Полученные условия являются достаточно конструктивными и сводятся к анализу знаков корней некоторого полинома от одной переменной. Вместе с тем, вовсе не исследовался случай, когда одна поверхность находится целиком внутри другой; кроме того, обобщение предлагаемого подхода на случай п > 3 не было предложено (и кажется проблематичным).

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

Пусть в М" заданы два алгебраических многообразия. Первое из них является квадрикой

ХТА1Х + 2В\X -1 = 0 (как правило, эллипсоидом), а вторая — либо линейным многообразием с\х = /¿1,., С^Х = либо же квадрикой

ХтА2Х + 2В\Х -1 = 0.

Требуется

1) найти необходимые и достаточные условия пересечения этих многообразий и, в случае отсутствия пересечения,

2) найти расстояние между многообразиями;

3) найти координаты их ближайших точек;

4) произвести анализ алгоритмов на предмет зависимости уравнений от параметров.

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

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

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

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

1) нахождение условий пересечения эллипсоида и линейного многообразия, и в случае их непересечения вычисление расстояния между этими поверхностями как корня алгебраического уравнения,

2) нахождение условий пересечения эллипсоида и квадрики, и в случае их непересечения вычисление расстояния между поверхностями как корня алгебраического уравнения,

3) нахождение ближайших точек рассмотренных поверхностей,

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

Методы исследований. Применением метода множителей Лагран-жа задача сводится к решению системы алгебраических уравнений. Для решения этой системы предлагается использовать не численные (итерационные) методы, а аналитические — технику многомерных результантов для исключения переменных в системах алгебраических уравнений. Именно этот альтернативный подход к решению классической задачи является принципиально новым.

Основные положения, выносимые на защиту:

1) критерий проверки пересечения алгебраических поверхностей в К": эллипсоида и линейного многообразия, эллипсоида и квадрики;

2) метод нахождения расстояний между указанными поверхностями;

3) нахождение расстояния от заданной точки до эллипса в М2, движущегося по уникурсальной траектории;

4) метод нахождения ближайших точек поверхностей во всех указанных задачах;

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

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

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

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

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

• международном математическом конгрессе ICM'06 (Мадрид);

• международном конгрессе по индустриальной и прикладной математике 1С1АМ'07 (Цюрих);

• международной конференции "Компьютерная алгебра в научных вычислениях" CASC'07 (Бонн);

• научных конференциях "Процессы управления и устойчивость" факультета прикладной математики - процессов управления Санкт

Петербургского государственного университета (С.-Петербург, 2005 и 2006 гг.);

• семинарах кафедры математического моделирования энергетических систем факультета прикладной математики - процессов управления.

Публикации. По материалам диссертации опубликованы 7 работ, 3 из которых в изданиях, входящих в перечень ВАК рецензируемых научных журналов [22, 28, 47].

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы; она включает 113 листов машинописного текста, 9 рисунков, список цитируемой литературы состоит из 48 наименований.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Яшина, Марина Витальевна

ЗАКЛЮЧЕНИЕ

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

1) критерий проверки пересечения алгебраических поверхностей в Мп: эллипсоида и линейного многообразия, эллипсоида и квадрики;

2) метод нахождения расстояний между указанными поверхностями;

3) нахождение расстояния от заданной точки до эллипса в М2, движущегося по уникурсальной траектории;

4) метод нахождения ближайших точек поверхностей во всех указанных задачах;

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

Список литературы диссертационного исследования кандидат физико-математических наук Яшина, Марина Витальевна, 2009 год

1. Бохер, М. Введение в высшую алгебру / М. Бохер ; пер. А.Г. Курош. М. : ЛКИ, 2008. - 296 с.

2. Bpio, Ш. Аналитическая геометр1я / Ш. Bpio и Ж.К. Буке ; пер. В. Синцов. — СПб.-М. : Издаше книгопродавца-типографа М.О.Вольфа, 1868. 508 с.

3. Галеев, Э.М. Оптимизация: теория, примеры, задачи / Э.М. Галеев, В.М. Тихомиров. М. : Эдиториал УРСС, 2000. - 320 с.

4. Гантмахер, Ф.Р. Теория матриц / Ф.Р. Гантмахер. — М. : Физмат-лит, 2004. 560 с.

5. Гельфанд, И.М. Лекции по линейной алгебре / И.М. Гельфанд. — М. : МЦНМО, 2007. 320 с.

6. Гурса, Э. Курсъ математическаго анализа: в 3 т. Т. 1. Производныя и дифференциалы. Определнные интегралы. Разложение в ряды. Геометрическия приложения. / Э. Гурса ; пер. А.И. Некрасов. — М. : Издание торгового дома "В.И.Знаменский и К°", 1911. — 630 с.

7. Зиновьев, А.Ю. Визуализация многомерных данных / А.Ю. Зиновьев. — Красноярск : Изд. КГТУ, 2000. 168 с.

8. Калинина, Е.А. Теория исключения: учебное пособие / Е.А. Калинина, А.Ю. Утешев. СПб. : НИИ Химии СПбГУ, 2002. - 72 с.

9. Куржанский, A.B. Задачи динамики и управления в гибридных системах / A.B. Куржанский, П. Варайя // Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби : тр. международ. сем. / Екатеринбург , 2005. С. 74-81.

10. Лаврентьев, M. Основы вариационного исчисления: в 2 т. Т. 1. 4.II. Функции многих переменных / М. Лаврентьев, Л. Люстерник. — город : ОНТИ НКТП, 1935. 400 с.

11. Лагутин, М.Б. Наглядная математическая статистика / М.Б. Лагутин. — М. : БИНОМ. Лаборатория знаний, 2007. — 472 с.

12. Огородова, Л.В. Высшая геодезия: в 3 ч. Ч. 3. Теоретическая геодезия: учебник для вузов / Л.В. Огородова. — М. : Геодезкартиздат, 2006. 381 с.

13. Проскуряков, И.В. Сборник задач по линейной алгебре / И.В. Проскуряков. — М. : Наука, 1974. — 384 с.

14. Рашевский, П.К. Курс дифференциальной геометрии / П.К. Ра-шевский. — М. : Эдиториал УРСС, 2003. — 428 с.

15. Розенфельд, Б.А. Аполлоний Пергский / Б.А. Розенфельд. — М. : МЦНМО, 2004. 176 с.

16. Садовничий, В.А. Задачи студенческих математических олимпиад / В.А. Садовничий, A.A. Григорьян, C.B. Конягин. — М. : МГУ, 1987. — 310 с.

17. Смирнов, В.И. Курс высшей математики: в 5 т. Т. 2. / В.И. Смирнов. — СПб. : BHV-Санкт-Петербург, 2008. — 848 с.

18. Смирнов, В.И. Курс высшей математики: в 5 т. Т. 5. / В.И. Смирнов. — М. : Наука, 1959. — 657 с.

19. Утешев, А.Ю. К задаче полиномиальной оптимизации / А.Ю. Уте-шев, Т.М. Черкасов // Доклады РАН. — 1998. Т. 361. - №2. — С. 168-170.

20. Утешев, А.Ю. Нахождение расстояния от эллипсоида до плоскости и квадрики вГ / А.Ю. Утешев, М.В. Яшина // Доклады Академии наук. 2008. - Т. 419. - №4. - С. 471-474.

21. Фаддеев, Д.К. Вычислительные методы линейной алгебры / Д.К. Фаддеев, В.Н. Фадеева. — СПб. : Лань, 2002. — 736 с.

22. Фаддеев, Д.К. Лекции по алгебре / Д.К. Фаддеев. — СПб. : Лань, 2004. — 416 с.

23. Хорн, Р. Матричный анализ / Р. Хорн, Ч. Джонсон ; пер. Х.Д. Икрамов. — М. : Мир, 1989. — 656 с.

24. Чезаро, Э. Элементарный учебник алгебраического анализа и исчисления бесконечно малых /Э. Чезаро ; пер. К.А. Поссе. — Одесса : Ма!;!^, 1913. — 632 с.

25. Шилов, Г.Е. Математический анализ (функции нескольких вещественных переменных): в 3 ч. Ч. 1-2. / Г.Е. Шилов. — М. : Наука, 1972. — 624 с.

26. Яшина, М.В. О метрической проблеме для поверхностей второго порядка вГ / М.В. Яшина // Вестник СПбГУ. Серия 10 (прикладная математика). — 2008. — Вып. 3. — С. 53—57.

27. Algebraic Geometry and Geometric Modeling : сб. ст. / под ред. L. González-Vega. AGGM'06, Barcelona, 2006. - 139 P.

28. Bikker, P. On the Bézout construction of the resultant / P. Bikker, A.Yu. Uteshev // J. Symb. Comput. 1999. - V. 28. - M. P. 4588.

29. Bischoff, S. Ellipsoid decomposition of 3D-models / S. Bischoff, L. Kobbelt // Proceedings on First International Symposium on 3D Data Processing Visualization and Transmission. — 2002. — P. 480—488.

30. Chen, X-D. Computing minimum distance between two implicit algebraic surfaces / X-D. Chen, J-H. Yong, G-Q. Zheng, J-C. Paul, J-G. Sun // Computer-Aided Design. 2006. - V. 38. - P. 10531061.

31. Encyklopádie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen. Bd. I. Arithmetik und Algebra / под ред. W.F. Meyer. — Leipzig : Teubner, 1898-1904.

32. Fitzgibbon, A. Direct least square fitting of ellipses / A. Fitzgibbon, M. Pilu, R.B. Fisher // IEEE transactions on pattern analysis and machine intelligence. — 1999. — V. 21. — №5. P. 476-480.

33. Kurzhanskiy, A.B. On ellipsoidal techniques for reachability analysis. Parts I,II / A.B. Kurzhanskiy, P. Varaiya // Optimization Methods and Software. 2002. - V. 17. - P. 187-237

34. Kurzhanskiy, A.A. Ellipsoidal toolbox (ET) / A.A. Kurzhanskiy, P. Varaiya // 45th IEEE Conference on Decision and Control / 13—15 Dec. 2006. P. 1498-1503.

35. Lin, A. A class of methods for projection on the intersection of several ellipsoids / A. Lin, S-P. Han // SIAM J.Optim. 2004. - V. 15. -№. - P. 129-138.

36. Lin, A. On the distance between two ellipsoids / A. Lin, S-P. Han // SIOPT. 2002. - V. 13. - Issue 1. - P. 298-308.

37. Olivik, S. / Position of reflecting points in bistatic satellite altimetry: theretical solutions for ellipsoid / S. Olivik, M. Kocandrlova, J. Kostelecky, J. Klokocnik // European Geosciences Union. Vienna, 2006. / 02-07 April 2006. P. 153.

38. Preparata, F.P. Computational geometry / F.P. Preparata, M.I. Shamos NY : Springer, 1985. - 398 P.

39. Schneider, P.J. Geometric tools for computer graphics /P.J. Schneider, D.H. Eberly — San Francisco : Elsevier, 2003. — 1009 P.

40. Wang, W. An algebraic condition for the separation of two ellipsoids / W. Wang, J. Wang, M-S. Kim // Computer Aided Geometric Design. 2001. - V. 18. - P. 531-539.

41. Wang, W. Efficient collision detection for moving ellipsoids using separating planes / W. Wang, Y-K. Choi, B. Chan, M-S. Kim, J. Wang // Computing. 2004. - V. 72. - P. 235-246.

42. Uteshev, A.Yu. Distance computation from an ellipsoid to a linear or quadric surface in Mn / A.Yu. Uteshev, M.V. Yashina // International

43. Congress of Mathematicians. Madrid, 2006 : abstracts / European Mathematical Society, 2006. — P. 504.

44. Yashina, M. Distance evaluation between quadric surfaces in Rn / M. Yashina, A. Uteshev // 6th International Congress on Industrial and Applied Mathematics. Zurich, 2007 : abstracts / 16—20 July 2007. — P. 444.