|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Davydov 2:5020/400 31 Jan 2002 10:08:45
To : Dennis
Subject : Re: circles
--------------------------------------------------------------------------------
> From: Dennis <denis@tversu.ru>
> Date: Tue, 29 Jan 2002 13:03:50 +0000 (UTC)
>
>Есть задача. Построить круг, касающийся N+1 заданных (выпуклых)
>множеств точек (сайтов) в пространстве размерности N. Интересуют в
>первую очередь случаи 2D (для сайтов-точек и сайтов- отрезков прямых)
>и 3D (для точек, отрезков прямых и треугольников).
Вообще-то, задача неоднозначна. К примеру, для N=1 (два отрезка на прямой)
существует четыре касающихся окружности, для N=2 - восемь, и так далее.
Даже если потребовать, чтобы сайты целиком находились вне круга, можно
придумать расположение (2D: первый сайт - отрезок |(-1,-1)(-1,1)|, второй -
точка (0,0) и третий - отрезок |(1,-1)(1,1)|), при котором существует
более одного решения. Так что уточняй условие.
>Может быть, есть еще какие-то варианты решения этой задачи?
Если сайты есть многоранники одинаковой размерности с небольшим числом
граней, то можно попробовать найти минимум целевой функции (суммарного
объёма сайтов, отсекаемого кругом) на N+1-мерном векторе (координаты
центра и радиус) при граничных условиях (ненулевой объём, отсекаемый
от каждого сайта) стандартными методами нелинейной оптимизации...
Вал. Дав.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: circles 