|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dennis 2:5020/400 29 Jan 2002 17:03:50
To : All
Subject : circles
--------------------------------------------------------------------------------
Добрый день!
Есть задача. Построить круг, касающийся N+1 заданных (выпуклых)
множеств точек (сайтов) в пространстве размерности N. Интересуют в
первую очередь случаи 2D (для сайтов-точек и сайтов- отрезков прямых)
и 3D (для точек, отрезков прямых и треугольников).
В принципе, для интересующих множеств в 2D алгоритм относительно не
сложен. Hо уже там получается 4 разных сочетания, в каждом из которых
возможны еще несколько вариантов. Для 3D случая это дело становится
неподъемным. Hужен более универсальный метод.
Мы придумали такой (итерационный) алгоритм: на очередном шаге имеем на
каждом из сайтов по точке; ищем окружность, проходящую через эти
точки; в качестве очередных приближений берем проекции этих точек на
сайты.
Известен ли этот алгоритм? Как можно доказать его сходимость? В
некоторых частных случаях я могу доказать, что описанный алгоритм
эквивалентен методу Hьютона (касательных), т.е. имеет квадратичную
скорость сходимости. Hо желательно доказать для общего случая или, в
по крайней мере, для указанных выше вариантов...
Может быть, есть еще какие-то варианты решения этой задачи?
--
Best regards,
Dennis
mailto: denis@tversu.ru
ICQ: 21938733
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Tver State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
